Lab4 - Preemptive Multitasking需要在多个同时激活的用户模式环境中实现抢占式多任务。
实验分为三个部分。第一部分要求为JOS添加多处理器支持,并实现论询调度以及基本的环境管理系统调用;第二部分需要实现一个Unix-like的fork函数,使得用户环境可以创建一份自己的拷贝;第三部分需要实现进程间通讯功能,允许不同的用户环境显式地互相通信和同步。同时还需要实现对于硬件时钟中断和抢占的支持。
2018年3月2日,完成了实验并写完了报告。

实验准备

根据官网,切换到分支lab4并合并分支lab3。在合并的过程中,发生了冲突。

1
2
user% git checkout -b lab3 origin/lab3
user% git merge lab3

根据提示,是conf/lab.mk中发生了冲突。打开后可以发现是其中记录的时间和实验数发生了变化,直接采用分支lab4的版本即可,然后提交,分支合并完成。

实验四包括如下的新文件:

  • kern/cpu.h 内核私有的关于多处理器的支持
  • kern/mpconfig.c 读取多处理器配置的代码
  • kern/lapic.c 内核驱动每个处理的的APIC(高级可编程中断控制器)的代码
  • kern/mpentry.S 非引导CPU的汇编入口代码
  • kern/spinlock.h 内核私有的自旋锁定义,包括大内核锁
  • kern/spinlock.c 内核实现自旋锁的代码
  • kern/sched.c 需要实现的调度器的代码框架

实验过程

第一部分 Multiprocessor Support and Cooperative Multitasking - 多处理器支和写作式多任务

在第一部分中,需要使JOS运行在一个多处理器系统上,并且实现新的JOS内核系统调用去允许用户级别的环境创建额外的新环境。还需要实现协同式的论询调度,允许内核当旧的用户环境自愿放弃CPU或退出时切换至一个新的用户环境。

多处理器支持

需要使JOS支持“对称多处理”(Symmetric Multiprocessing),在该模型下,所有的CPU都有着对系统资源(内存、IO总线等)的平等访问权。尽管在SMP下所有的CPU在功能上均等价,在启动时仍然分为两种类型——引导处理器(Bootstrap Processor或是BSP)负责初始化系统并且引导操作系统;应用处理器(Application Processors或是APs)仅在系统启动运行后被BSP激活。BSP处理器由硬件和BIOS决定。在此刻,所有已有的代码已经运行在了BSP上。

在SMP中,每一个CPU都有一个相伴的本地APIC(LAPIC)单元。LAPIC单元负责在整个系统中传递中断。LAPIC为相连的CPU提供了一个唯一标识。在本实验中,将利用LAPIC的一下功能(在kern/lapic.c中):

  • 读取LAPIC标识(APIC ID)以告知CPU代码运行在哪一个CPU上(参考cpunum()
  • 从BSP向APs发送STARTUP处理器间中断(Interprocessor interrupt或IPI)以唤醒其他CPU(参考lapic_startup()
  • 在第三部分中,通过编程LAPIC内置的计时器去引发时钟中断以实现抢占式多任务(参考apic_init()

处理器通过内存映射IO(Memory-mapped I/O 或是MMIO)访问LAPIC。在MMIO中,一部分物理内存被硬连接至某些IO设备的寄存器。所以相同的访问内存的load/store指令可以被用来访问设备寄存器。你可能已经见过了存在于物理地址0xA0000中IO洞(以此来写VGA显示缓存)。LAPIC存在于物理地址从0xFE000000(4064M)开始的洞中。该地址太高以至于无法在KERNBASE的直接映射访问。JOS的虚拟内存映射在MMIOBASE处留下了4MB的空隙。在之后的实验中会引入更多的MMIO区域,所以应当写一个简单的函数从该区域分配空间并映射内存。

练习1的答案如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// In kern/pmap.c, mmio_map_region():
// Your code here:
size = ROUNDUP(size, PGSIZE);
if (base + size > MMIOLIM) {
// reservation overflog MMIOLIM
panic("reservation bytes overflows!");
}

// use boot_map_region to map [pa, pa + size) to [base, base + size)
boot_map_region(kern_pgdir, base, size, pa, PTE_W | PTE_PCD | PTE_PWT);

// update base and return
uintptr_t saved_base = base;
base += size;
return (char *)saved_base;

// panic("mmio_map_region not implemented");

应用处理器引导

BSP在引导APs之前应当首先收集多处理器系统的信息,如总CPU数,APIC IDs以及LAPIC单元的内存映射IO地址等。kern/mpconfig.c中的mp_init()函数通过读取BIOS内存中的MP配置表获取相应的信息。
kern/init.c中的boot_aps()函数驱动AP引导过程。APs在实模式中启动,所以boot_aps()kern/mpentry.S中拷贝AP入口代码到一个实模式可寻址的位置。可以在一定程度上控制AP执行开始代码的位置。在本实验中,将入口代码拷贝至0x7000(MPENTRY_PADDR),但实际上任何640KB以下的、页对齐的和未使用的物理地址均可使用。
然后,boot_aps()通过向对应AP的LAPIC单元发送STARTUP处理器间中断和初始的CS:IP地址(本实验中为MPENTRY_PADDR),依次激活APs。在简单的设置后,将AP启动分页,使得AP进入保护模式,然后调用启动例程mp_main()(在kern/init.c中。boot_aps()在唤醒下一个AP之前先等待当前AP在struct CpuInfocpu_status域中发送一个CPU_STARTED标记。
AP引导的汇编代码和C代码同实验一BSP的引导代码相似,可以比对异同。

练习2的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// In kern/pmap.c, page_init():
// code MODIFIED
size_t i;

// initialize from page 1 to page npages_basemem - 1
// set pp_ref to 0, set pp_link to last page_free_list
// and then update page_free_list

// Lab 4: remove page at MPENTRY_PADDR
size_t mp_entry_page = PGNUM(MPENTRY_PADDR);

for(i = 1 ; i < npages_basemem ; i++) {
if (i == mp_entry_page) {
continue;
}
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}

问题1:
MPBOOTPHYS作用是将给定的内核虚拟地址(在mpentry.S中)转换成相应的加载后的物理地址。这么做的原因是在mpentry.S中,保护模式与分页机制尚未开启,设置分段等需要知道相应的物理地址。

每CPU状态和初始化

当编写多处理器操作系统时,区分对于每个处理器而言私有的每CPU状态以及整个系统共享的全局状态是很重要的。kern/cpu.h定义了大部分每CPU状态,包括了存储了每CPU变量的struct CpuInfocpunum()总是返回调用它的CPU ID,能用来索引例如cpus的数组。宏thiscpu是当前CPU的struct CpuInfo的简写。

以下是你需要注意的每CPU状态:

  • 每CPU内核栈 - 多个CPU可能会同时陷入内核,因此每个处理器需要独立的内核栈以避免互相干扰。percpu_kstacks[NCPU][KSTKSIZE]NCPU个内核栈预留空间。在实验二中,将bootstack指向的物理内存作为BSP的栈映射在了KSTACKTOP下面。相似地,本实验中,需要将每个CPU的内核栈映射到该区域同时分配保护页作为它们之间的缓冲。CPU 0的栈将从KSTACKTOP开始向下增长;CPU 1的栈将从CPU 0栈下方间隔KSTKGAP处开始增长。inc/memlayout.h展示了映射约束。
  • 每CPU的TSS和TSS描述符 - 每CPU的任务状态段同样用来致命每个CPU内核栈的位置。CPU i的TSS被存储于cpus[i].cpu_ts中,相应的TSS描述符在GDT入口gdt[(GD_TSS0 >> 3) + i]处被定义。kern/trap.c中定义的ts将不再有效。
  • 每CPU的当前环境指针 - 由于每个CPU都能同步地执行不同的用户环境。重新将curenv定义为指向当前CPU(当前代码正在执行的CPU)正在执行的环境的cpus[cpunum()].cpu_env(或是thiscpu->cpu_env)。
  • 每CPU的系统寄存器 - 包括系统寄存器在内的所有寄存器都属于CPU私有。因此初始化这些寄存器的指令如lcr3, ltr, ‘lgdt’等,必须在每个CPU上都被执行。函数env_init_percpu()以及trap_init_percpu正是为此而被定义。

除此之外任何额外的用来CPU初始化的所有每CPU状态都应该在每个CPU处重复。

练习3中遇到的问题:

  • 在使用boot_map_region映射内存时忘记将kstacktop_i减去KSTKSIZE,导致未通过检查

练习3的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
// LAB 4: Your code here:
size_t i;

for (i = 0; i < NCPU; i++) {
// traverser through 0 to NCPU to use boot_map_region to map
// per-CPU's kernel stack to corresponding va
uintptr_t kstacktop_i = KSTACKTOP - i * (KSTKSIZE + KSTKGAP);
boot_map_region(kern_pgdir, kstacktop_i - KSTKSIZE, KSTKSIZE,
PADDR(percpu_kstacks[i]), PTE_W | PTE_P);
}

练习4中遇到的问题:

  • 使用ltr加载任务段选择子时,每个CPU应当使用不同的选择子,inc/memlayout.c中的GD_TSS0为CPU0的任务段选择子,应该加上i << 3的偏移
  • 完成trap_init_percpu()后,旧的使用ts的代码应当被注释

练习4的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// LAB 4: Your code here:
// trap_init_percpu() is called by all CPUs
// set esp0 and ss0 of task state segment to provide
// per-CPU's kernel stack access
thiscpu->cpu_ts.ts_esp0 = (uintptr_t)percpu_kstacks[cpunum()];
thiscpu->cpu_ts.ts_ss0 = GD_KD;
// set IO map base address to prevent unauthorized environments
// this line works together as we'll set TSS segment limit later
// so all ports in address space have no corresponding IOPB
thiscpu->cpu_ts.ts_iomb = sizeof(struct Taskstate);

// set TSS in gdt
// 0 means RPL and sd_s = 0 means system segment
gdt[(GD_TSS0 >> 3) + cpunum()] = SEG16(STS_T32A, (uint32_t)(&(thiscpu->cpu_ts)),
sizeof(struct Taskstate) - 1, 0);
gdt[(GD_TSS0 >> 3) + cpunum()].sd_s = 0;

// Load TSS selector
ltr(GD_TSS0 + (cpunum() << 3));

// load the IDT
lidt(&idt_pd);

同步锁

当前的代码在mp_main()中初始化完AP之后忙等待。在继续下一步之前,首先得解决多个CPU同时执行内核代码时的竞争条件。最简答的方式是使用一个“大”内核锁,大内核锁在从用户模式进入内核模式时被获取,在从环境返回用户模式时被释放。在这种模型下,用户模式环境可以在任意多个CPU上运行,但同时只能有一个环境能在内核中运行,其他想在内核中运行的环境被强制等待。

kern/spinlock.h声明了内核锁,同时提供了lock_kernel提供加锁的功能;unlock_kernel提供解锁的功能,你应当在如下4个地方应用内核锁:

  • i386_init()中,在BSP唤醒其他CPU之前加锁
  • mp_main()中,在初始化AP后加锁,然后调用sched_yield()去在当前AP上执行环境
  • trap()中,当从用户模式陷入的时候加锁,通过检查tf_cs的低位判断陷阱发生于用户模式还是内核模式
  • env_run()中,在“刚好”切换回用户模式之前解锁。太早或太晚解锁会导致严重的竞争和死锁

练习5的代码如下,仅供参考:

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
// In i386_init():
// Acquire the big kernel lock before waking up APs
// Your code here:
lock_kernel();

// In mp_main():
// Now that we have finished some basic setup, call sched_yield()
// to start running processes on this CPU. But make sure that
// only one CPU can enter the scheduler at a time!
//
// Your code here:
// lock the kernel and start running enviroments
lock_kernel();
sched_yield();

// In trap():
// Trapped from user mode.
// Acquire the big kernel lock before doing any
// serious kernel work.
// LAB 4: Your code here.
lock_kernel();

// In env_run():
// address space switch
// reference from inc/x86.h
lcr3(PADDR(e->env_pgdir));
// release kernel lock here
unlock_kernel(); // newly added code
// drop into user mode
env_pop_tf(&(e->env_tf));

问题2:
即使受到内核锁的保护,CPU之间仍然需要独立的内核栈。假设CPU0因中断陷入内核并在内核栈中保留了相关的信息,此时若CPU1也发生中断而陷入内核,在同一个内核栈的情况下,CPU0中的信息将会被覆盖从而导致出现错误。

论询调度

下一个任务是改变JOS内核使得其能按照“论询”的方式在多个环境中切换。在JOS中,论询调度按如下方式工作:

  • ‘kern/sched.c’中的sched_yield()负责选择一个新环境执行。其循环按顺序遍历envs数组,从上一次运行的环境(如果没有之前运行的环境,则从第一个环境)开始,找到第一个具有状态ENV_RUNNABLE的环境,调用env_run()执行。
  • sched_yield()绝对不能同时在两个CPU上运行相同的环境。其会告知环境当前已经正在运行在某CPU上(很可能是当前环境),因为该环境的状态将为ENV_RUNNING。
  • 将实现一个新的系统调用sys_yield(),用户环境可以通过该系统调用唤醒sched_yield()函数以主动放弃CPU。

练习6中遇到的问题:

  • 在实现sched_yield()的时候没有检查thiscpu->cpu_env是否为空,对空指针的访问导致了缺页错误
  • 一开始的实现弄错了获取env_index和自增的顺序,参考代码中第一个if处的else分支的注释
  • 练习6结束后需要将init.cmp_main()的最后一行注释

练习6的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// In kern/sched.c, sched_yield():
// LAB 4: Your code here.
// get index from current CPU's env
size_t env_index;
// set curenv_flag to default true
int curenv_flag = true;

size_t i;
if (thiscpu->cpu_env == NULL) {
// no previous running environment
// start at beginning of envs array
i = 0;
env_index = NENV - 1;
// mark curenv_flag as true
curenv_flag = false;
} else {
// start at previous running environment
env_index = ENVX(thiscpu->cpu_env->env_id);
// NB: don't mess with code order here, must first retrieve
// env_index then increment
i = (env_index == NENV - 1) ? 0 : env_index + 1;
}
// traverse through envs list to find first ENV_RUNNABLE
// env
for (; i != env_index; i = ((i == NENV - 1) ? 0 : i + 1)) {
if (envs[i].env_status == ENV_RUNNABLE) {
// found, set idle and break from loop
idle = &envs[i];
break;
}
}

// if idle is NULL and curenv_flag is true,
// means no envs are runnable and last previous running env is ENV_RUNNING
// check if last previous environment is ENV_RUNNING,
// if so, choose it.
if (!idle && curenv_flag && envs[env_index].env_status == ENV_RUNNING) {
idle = &envs[env_index];
}

if (idle) {
// idle env choosed, run it directly
env_run(idle);
} else {
// failed to choose idle env, halt CPU
// sched_halt never returns
sched_halt();
}

// In kern/syscall.c, syscall():
// code added:
case SYS_yield:
// call sys_yield
sys_yield();
break;

// In kern/init.c, i386_init():
// code modified:
#if defined(TEST)
// Don't touch -- used by grading script!
ENV_CREATE(TEST, ENV_TYPE_USER);
#else
// Touch all you want.
// create three user_yield
// code MODIFIED here
ENV_CREATE(user_yield, ENV_TYPE_USER);
ENV_CREATE(user_yield, ENV_TYPE_USER);
ENV_CREATE(user_yield, ENV_TYPE_USER);
#endif // TEST*

问题3:
地址切换前后的页表中,e指向的虚拟地址都被同一块物理页映射。出现这种情况的原因在于envenv_pgdir是以kern_pgdir为原型产生的,e出于UTOP之上的地址,而UTOP以上的地址的映射关系在两个页表中是一样的。

问题4:
当发生地址转换时一定是从用户陷入内核之后,无论以何种方式陷入内核,必须要经过kern/trap.c中的trap()函数。观察该函数,可以发现,当从用户模式陷入内核时,代码将内核栈中的tf(包括页表和寄存器等)拷贝至内核间共享的对应的env中,所以之后寄存器状态才能恢复。

环境创建的系统调用

尽管内核已经可以运行并在不同环境间切换了,但内核任然被限制了只能执行内核初始设置的用户环境。
需要实现必要的系统调用使得JOS可以允许用户环境创建和启动其他的用户环境。

Unix提供了fork()作为它的进程创建原语。Unix的fork()拷贝调用进程(父进程)的整个地址空间以创建子进程。
从用户空间来看,父子进程唯一可观察的差异就是它们的进程ID和父进程ID(通过gitpid()getppid()返回。在父进程中,fork()返回子进程ID;在子进程中,fork()返回0。默认情况下,每个进程均获得其私有的地址空间,并且任意一个进程对于内存的修改对于其他进程都是不可见的。

将要实现一个不同的、更加原始的JOS系统调用原语集合去创建新的用户模式环境,通过这些系统调用,除了其他类型的环境创建以外,将能够在用户空间实现一个完整的类Unixfork()系统调用。需要实现的系统调用为:

  • sys_exofork - 创建一个几乎空白的新环境:在地址空间没有任何的用户映射,并且也无法运行。新环境将会有和父环境在执行sys_exofork系统调用时完全一致的寄存器状态。在父进程中,sys_exofork会返回新创建环境的envid_t(若环境创建错误则返回一个错误码);子进程则会返回0(因为子进程最初被标记为不可运行,直到父进程通过显式标记子进程可运行之后,sys_exofork返回。
  • sys_env_set_status - 设置指定的环境的状态为ENV_RUNNABLE或是ENV_NOT_RUNNABLE。该系统调用通常在一个新环境的地址空间和寄存器状态完全初始化之后标记其为可运行。
  • sys_page_alloc - 分配一页的物理内存并将其映射到给定环境地址空间的给定虚拟地址。
  • sys_page_alloc - 将一页映射(而不是实际的页内容)从一个环境的地址空间拷贝至另一个,共享内存使得新映射和旧映射指向同一页物理内存。
  • sys_page_unmap - 将给定环境的给定虚拟地址的页面解除映射。

上述所有的系统调用接受环境ID,内核支持将0到“当前环境”转换,在kern/env.c中的envid2env()实现。

已经在user/dumpfork.c中提供了非常原始的类Unix的fork()实现。测试程序用上述系统调用创建并运行一个当前地址空间拷贝的子进程,然后两个环境使用sys_yield()来回切换。父进程在10次迭代后退出;子进程在20次迭代后退出。

练习7的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
// In sys_exofork():
// Allocate a new environment.
// Returns envid of new environment, or < 0 on error. Errors are:
// -E_NO_FREE_ENV if no free environment is available.
// -E_NO_MEM on memory exhaustion.
static envid_t 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.
// get env_id of current environment
envid_t parent_id = thiscpu->cpu_env->env_id;

// use env_alloc to create new environment and
// do some basic setup(status and register set)
struct Env *env = NULL;
if (env_alloc(&env, parent_id) < 0) { panic("sys_exofork failed!"); }
env->env_status = ENV_NOT_RUNNABLE;
env->env_tf = thiscpu->cpu_env->env_tf;

// do the trick to set eax register of newly
// alloc environment to 0
env->env_tf.tf_regs.reg_eax = 0;

// return new environment's ID
return env->env_id;

// panic("sys_exofork not implemented");
}

// In sys_env_set_status():
// Set envid's env_status to status, which must be ENV_RUNNABLE
// or ENV_NOT_RUNNABLE.
//
// Returns 0 on success, < 0 on error. Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist,
// or the caller doesn't have permission to change envid.
// -E_INVAL if status is not a valid status for an environment.
static int 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.
// check status passed in
if (status != ENV_RUNNABLE && status != ENV_NOT_RUNNABLE) {
// invalid status
return -E_INVAL;
}

struct Env *env;
// call envid2env to translate envid passed in
if (envid2env(envid, &env, true) < 0) {
// bad environment
return -E_BAD_ENV;
}
// set status
env->env_status = status;

// panic("sys_env_set_status not implemented");

return 0;
}

// In sys_page_alloc():
// Allocate a page of memory and map it at 'va' with permission
// 'perm' in the address space of 'envid'.
// The page's contents are set to 0.
// If a page is already mapped at 'va', that page is unmapped as a
// side effect.
//
// perm -- PTE_U | PTE_P must be set, PTE_AVAIL | PTE_W may or may not be set,
// but no other bits may be set. See PTE_SYSCALL in inc/mmu.h.
//
// Return 0 on success, < 0 on error. Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist,
// or the caller doesn't have permission to change envid.
// -E_INVAL if va >= UTOP, or va is not page-aligned.
// -E_INVAL if perm is inappropriate (see above).
// -E_NO_MEM if there's no memory to allocate the new page,
// or to allocate any necessary page tables.
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.
struct Env *env;
// check and get env
if (envid2env(envid, &env, true) < 0) {
// envid not exist or permission error
return -E_BAD_ENV;
}

// check va
if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) {
// va above UTOP or va is not page-aligned
return -E_INVAL;
}

// check perm
if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
// invalid perm
return -E_INVAL;
}

// allocate page and then insert it
// check if out of memory
struct PageInfo *page;
if ((page = page_alloc(ALLOC_ZERO)) == NULL) {
// failed to allocate page
return -E_NO_MEM;
}
if (page_insert(env->env_pgdir, page, va, perm) < 0) {
// page table couldn't be allocated
// free ununsed page
page_free(page);
return -E_NO_MEM;
}

// panic("sys_page_alloc not implemented");

// page successfully allocated
return 0;
}

// In sys_page_map():
// Map the page of memory at 'srcva' in srcenvid's address space
// at 'dstva' in dstenvid's address space with permission 'perm'.
// Perm has the same restrictions as in sys_page_alloc, except
// that it also must not grant write access to a read-only
// page.
//
// Return 0 on success, < 0 on error. Errors are:
// -E_BAD_ENV if srcenvid and/or dstenvid doesn't currently exist,
// or the caller doesn't have permission to change one of them.
// -E_INVAL if srcva >= UTOP or srcva is not page-aligned,
// or dstva >= UTOP or dstva is not page-aligned.
// -E_INVAL is srcva is not mapped in srcenvid's address space.
// -E_INVAL if perm is inappropriate (see sys_page_alloc).
// -E_INVAL if (perm & PTE_W), but srcva is read-only in srcenvid's
// address space.
// -E_NO_MEM if there's no memory to allocate any necessary page tables.
static int sys_page_map(envid_t srcenvid, void *srcva, envid_t dstenvid,
void *dstva, int perm) {
// Hint: This function is a wrapper around page_lookup() and
// page_insert() from kern/pmap.c.
// Again, most of the new code you write should be to check the
// parameters for correctness.
// Use the third argument to page_lookup() to
// check the current permissions on the page.

// LAB 4: Your code here.
struct Env *srcenv, *dstenv;
// check environment
if ((envid2env(srcenvid, &srcenv, true) < 0) ||
(envid2env(dstenvid, &dstenv, true) < 0)) {
// srcenvid or dstenvid doesn't exist or
// caller doesn't have permissions
return -E_BAD_ENV;
}

// check srcva and dstva about address and page-aligned
// get srcenv and dstenv
if (((uintptr_t)srcva >= UTOP) || ((uintptr_t)dstva >= UTOP) ||
(PGOFF(srcva) != 0) || (PGOFF(dstva) != 0)) {
// addresses above UTOP or addresses not page_aligned
return -E_INVAL;
}

struct PageInfo *srcpage;
pte_t * scrpte_ptr;
// use page look up to get source page and corresponding pte_t *
if ((srcpage = page_lookup(srcenv->env_pgdir, srcva, &scrpte_ptr)) ==
NULL) {
// srcva not mapped in srcenvid's address space
return -E_INVAL;
}

// check perm passed in
if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
// invalid perm
return -E_INVAL;
}

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

// insert source page into dstenv's pgdir with perm
// check if out of memory
if (page_insert(dstenv->env_pgdir, srcpage, dstva, perm) < 0) {
// out of memory to allocate page table
return -E_NO_MEM;
}

// panic("sys_page_map not implemented");

// page successfully mapped
return 0;
}

// In sys_page_unmap():
// Unmap the page of memory at 'va' in the address space of 'envid'.
// If no page is mapped, the function silently succeeds.
//
// Return 0 on success, < 0 on error. Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist,
// or the caller doesn't have permission to change envid.
// -E_INVAL if va >= UTOP, or va is not page-aligned.
static int sys_page_unmap(envid_t envid, void *va) {
// Hint: This function is a wrapper around page_remove().

// LAB 4: Your code here.
struct Env *env;
// check and get env
if (envid2env(envid, &env, true) < 0) {
// envid not exist or permission error
return -E_BAD_ENV;
}

// check va
if ((uintptr_t)va >= UTOP || PGOFF(va) != 0) {
// va above UTOP or va is not page-aligned
return -E_INVAL;
}

// call page_remove to unmap page
page_remove(env->env_pgdir, va);

// panic("sys_page_unmap not implemented");

// page successfully unmapped
return 0;
}

// In syscall():
// new code added
case SYS_exofork:
// call sys_exofork
return sys_exofork();
break;
case SYS_env_set_status:
// call sys_env_set_status
return sys_env_set_status((envid_t)a1, (int)a2);
break;
case SYS_page_alloc:
// call sys_page_alloc
return sys_page_alloc((envid_t)a1, (void *)a2, (int)a3);
break;
case SYS_page_map:
// call sys_page_map
return sys_page_map((envid_t)a1, (void *)a2, (envid_t)a3, (void *)a4,
(int)a5);
break;
case SYS_page_unmap:
// call sys_page_unmap
return sys_page_unmap((envid_t)a1, (void *)a2);
break;

第二部分 Copy-on-Write Fork - 写时复制Fork

Unix提供了一个fork()系统调用作为其原始的进程创建原语。fork()系统调用将调用进程的整个地址空间拷贝以创建子进程。

xv6通过将父进程页中的所有数据复制到子进程中的新页中来实现fork(),这本质上就是dumbfowk()采用的方法。对于父进程地址空间的拷贝是整个fork()操作中最“贵”的部分。

然而,对于fork()的调用通常紧跟着一个对子进程的exec()系统调用,该系统调用用一个新程序替换子进程的内存,这就是一个典型的shell所做的。在这种情况下,花费的用于复制父进程的地址空间的时间是被浪费的,因为子进程在调用exec()前只会使用很少的内存。

出于以上的原因,Unix之后的版本利用了虚拟内存硬件去允许父进程和子进程共享映射到各自地址空间的内存,直到其中一个进程实际修改为止。该技术又被称作写时复制。
为了实现写时复制,在fork()中内核仅仅从父进程拷贝地址的映射而非实际映射的页面到子进程,并且在同时将共享的页面标记为只读。
当两个进程之一尝试写入其中一个共享页面时,该过程触发页面错误。
内核意识到该页面实际上是一个“虚拟”或是“写时复制”页面,所以其会创建一个错误页面的新的,私有的,可写的页副本。
通过这种方式,直到实际写入时,独立页面的内容才被复制。
该过程使得紧接着exec()fork()调用更加节约:子进程在调用exec()很可能只会复制一页(栈的当前页)。

本实验的下一个部分要求完成一个合适的类Unix的fork()的写时复制的实现(作为用户空间库例程)。在用户空间实现fork()并且支持写时复制使得内核能保留相对简洁,因此更不容易出现严重的错误。这同样可以允许独立的用户模式程序实现自己的fork()语义。

用户级别的页错误处理

用户级别的写时复制fork()实现需要知道写保护页面的页错误。写时复制只是用户级别的页错误处理的诸多可能用处之一。

通常的做法是设置一个地址空间以便页错误指示何时需要采取某些行动。大多数Unix内核通常只会为新进程的栈区域分配一页,随着进程栈逐渐增长直至访问到了还未被映射的栈地址,触发页错误,然后内核会“按需”分配更多的栈页面。
典型的Unix内核必须追踪进程的空间中的不同区域发生页错误时所采取的行动。栈区域的页错误通常会导致新页的分配和映射。BSS区域的页错误通常会导致分配一个新页,填充0,并映射。对于具有按需分页的可执行文件的系统,text段的页错误会导致内核从磁盘上的二进制文件读取相应的页面并映射。

内核需要追踪大量的信息。与传统的Unix方法不同,本实验需要用户决定如何处理用户空间中的每个页面错误,而这些错误的损害通常不大。这种设计还为程序定义存储区域带来了极大的灵活性。之后将会应用用户级别的错误处理程序来映射和访问基于磁盘的文件系统上的文件。

设置页错误处理程序

为了处理用户环境自己的页错误,用户环境必须向JOS内核注册一个页错误处理程序入口。用户环境通过sys_env_set_pgfault_upcall()的“上行”系统调用注册自己的错误处理程序入口。已经向struct Env添加了新的域env_pgfault_upcall来记录该信息。

练习8的代码如下,仅供参考:

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
// In sys_env_set_pgfault_upcall():
// Set the page fault upcall for 'envid' by modifying the corresponding struct
// Env's 'env_pgfault_upcall' field. When 'envid' causes a page fault, the
// kernel will push a fault record onto the exception stack, then branch to
// 'func'.
//
// Returns 0 on success, < 0 on error. Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist,
// or the caller doesn't have permission to change envid.
static int sys_env_set_pgfault_upcall(envid_t envid, void *func) {
// LAB 4: Your code here.
struct Env *env;
// check and translate the envid
if (envid2env(envid, &env, true) < 0) {
// envid not exist or permission error
return -E_BAD_ENV;
}

// set func
env->env_pgfault_upcall = func;

// panic("sys_env_set_pgfault_upcall not implemented");

return 0;
}

// In syscall():
// new code added
case SYS_env_set_pgfault_upcall:
// call sys_env_set_pgfault_upcall
return sys_env_set_pgfault_upcall((envid_t)a1, (void *)a2);
break;

用户环境中的正常栈和异常栈

在正常执行时,JOS中的用户环境会在正常栈中执行:正常栈的ESP寄存器指向USTACKTOP,并且压入的栈数据会存放于USTACKTOP - PGSIZE到USTACKTOP - 1的闭区域。
然而,当一个页错误在用户模式发生时,内核将重启用户环境,在一个另外的栈上运行一个特定的用户级别的页错误处理程序,该栈被称为用户异常栈。
实际上,将使JOS代表用户环境自动执行“栈切换”,就像x86处理器在用户模式转换到内核模式时已经代表JOS实现了栈切换一样。

JOS用户异常栈的大小也为一个页面大,栈顶被定义为指向虚拟地址UXSTACKTOP,用户异常栈的有效字节为UXSTACKTOP - PGSIZE到UXSTACKTOP - 1的闭区域。
当运行于异常栈上时,用户级别的页错误处理程序可以使用JOS的常规系统调用映射新的页或是调整页映射以修复任何可能导致页错误的问题。
然后用户级别的页错误处理程序通过汇编语言存根返回至原始栈上的错误代码处。

每一个想要支持用户级别页错误处理程序的用户环境需要自己为其异常栈通过sys_page_alloc()分配内存。

唤醒用户页错误处理程序

现在需要改变kern/trap.c中的页错误处理程序按特定的方式处理用户模式的页错误。
将错误时的用户环境状态叫做陷阱时状态。

若是没有页面错误处理函数被注册,则JOS内核会和之前一样,摧毁用户环境并输出一条消息。否则,内核会在异常栈设置在inc/trap.h中如struct UTrapFrame定义的陷阱帧。

然后内核会安排用户环境以页错误处理程序以上述栈帧在异常栈上恢复执行。fault_va是导致也错误的虚拟地址。

如果当异常发生时用户环境已经在用户异常栈上运行,则错误处理程序自身发生了错误。在这种情况下,你应当在当前的tf->tf_esp中而非UXSTACKTOP中重新启动栈帧。你应当首先压入一个4字节的字,然后一个struct UTrapFrame

检查tf->tf_esp是否在UXSTACKTOP - PGSIZE到UXSTACKTOP - 1的闭区间内来判断其是否已经在用户异常栈上。

练习9中遇到的问题:

  • curenv已经被重新定义为thiscpu->cpu_env,因此可以使用
  • 判断tf->tf_esp的if语句中,将与写成了或

练习9的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
// In trap.c, page_fault_handler():
// LAB 4: Your code here.
struct UTrapframe *utf;
uintptr_t utf_addr;

// check tf->tf_esp's location to calculate utf's address
if ((tf->tf_esp >= UXSTACKTOP - PGSIZE) && (tf->tf_esp < UXSTACKTOP)) {
// recursive case
// reason why here needs to substract a 4-byte word
// is to reserve space for reset eip/esp
utf_addr = tf->tf_esp - sizeof(struct UTrapframe) - 4;
} else {
// non-recursive case, set utf_addr to the top of
// user exception stack
utf_addr = UXSTACKTOP - sizeof(struct UTrapframe);
}

if (curenv->env_pgfault_upcall) {
// page fault upcall exist

// use mem assert to check environment allocates the exception
// stack and has write permission to it, and stack ISN'T overflow
// combine three case with only one user_mem_assert to check utf_addr
// NB: curenv HAS been redefined as thiscpu->cpu_env
user_mem_assert(curenv, (void *)utf_addr, sizeof(struct UTrapframe),
PTE_U | PTE_W | PTE_P);

// set user stack frame
utf = (struct UTrapframe *)utf_addr;
utf->utf_fault_va = fault_va;
utf->utf_err = tf->tf_err;
utf->utf_regs = tf->tf_regs;
utf->utf_eip = tf->tf_eip;
utf->utf_eflags = tf->tf_eflags;
utf->utf_esp = tf->tf_esp;

// modify stack frame to set entry for env_pgfault_upcall
// and set address for user exception stack
tf->tf_eip = (uintptr_t)curenv->env_pgfault_upcall;
tf->tf_esp = utf_addr;

env_run(curenv);
}

用户模式页错误入口

然后需要实现汇编例程,该例程调用C页错误处理程序,然后在恢复在原始的错误指令处的执行。该例程就是被sys_env_set_pgfault_upcall()注册的例程。

最后需要在C用户库实现用户模式的页错误处理机制。

练习10中遇到的问题:

  • 需要想清楚思路,即先将eip“压入”陷阱时栈中,使用一个sub后接一个mov指令来模拟该压栈过程,若为递归过程,则会将eip填入之前留下的空白。然后依次恢复寄存器以及eflags。最后pop %esp以切换栈并调用ret返回

练习10的代码如下,仅供参考:

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
// In pfentry.S:
// LAB 4: Your code here.
// push trap-time %eip to trap-time stack
// mov utf_eip to %eax
movl 0x28(%esp), %eax
// use sub and mov to *simulate* push
subl $0x4, 0x30(%esp)
movl 0x30(%esp), %ebp
movl %eax, (%ebp)
// pop the unused fault_va and err
popl %eax
popl %eax

// Restore the trap-time registers. After you do this, you
// can no longer modify any general-purpose registers.
// LAB 4: Your code here.
popal

// Restore eflags from the stack. After you do this, you can
// no longer use arithmetic operations or anything else that
// modifies eflags.
// LAB 4: Your code here.
addl $0x4, %esp
popfl

// Switch back to the adjusted trap-time stack.
// LAB 4: Your code here.
popl %esp

// Return to re-execute the instruction that faulted.
// LAB 4: Your code here.
ret

练习11中遇到的问题:

  • 注意描述,要使用_pgfault_upcall()(汇编例程包装)来注册用户页处理函数而非传入的那个函数

练习11的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// In set_pgfault_handler():
if (_pgfault_handler == 0) {
// First time through!
// LAB 4: Your code here.
// alloc one page for user exception stack
// and register user-level page fault upcall
if (sys_page_alloc(thisenv->env_id, (void *)(UXSTACKTOP - PGSIZE),
PTE_U | PTE_W | PTE_P) < 0) {
panic("failed to alloc page for user exception stack!");
}
if (sys_env_set_pgfault_upcall(thisenv->env_id, _pgfault_upcall) < 0) {
panic("failed to register page fault upcall!");
}

// panic("set_pgfault_handler not implemented");
}

faultalloc能成功而faultallocbad失败的原因在于faultallocbad直接使用系统调用输出,该输出会使用先使用内存检查而失败;而faultalloc使用了用户库中的cprintf,该函数在使用系统调用输出之前已经尝试对错误地址进行了解引用,触发了用户级别的缺页错误,在实际执行系统调用时,错误的地址已经被分配了页面,因此能通过内存检查。

实现写时复制

已经拥有了在用户空间中完整实现写时复制fork()的内核设施基础。

现在已经在lib/fork.c中给出了fork()的框架。同dumbfork()相似,fork()首先创建了一个新环境,然后扫描父进程的地址空间并在子进程中建立相同的页映射。核心区别在于dumbfork()复制页,而fork()只实现页映射的复制。fork()直到某环境尝试写时在复制对应的页。

fork()的基本控制流为:

  1. 父进程设置pgfault()作为C级别的页错误处理程序,使用实现了的set_pgfault_handler()函数
  2. 父进程调用sys_exofork()去创建子环境
  3. 对于地址空间中每一个在UTOP下的可写的或是写时复制的页面,父进程调用duppage(),该函数将该页面以写时复制映射进子进程然后在父进程的地址空间中重新映射该页面为写时复制(顺序很重要)。duppage()同时设置PTE,所以页面将不可写。通过avail域的PTE_COW区分写时复制页面和真正的只读页面。然而,异常栈却不按该方式重映射。需要为子进程分配一个新页面作为异常栈。由于页处理程序实际执行了页复制并且页处理程序运行于异常栈上,异常栈不能写时复制。fork()也需要处理存在但既不是写时复制也不是可写的页面。
  4. 父进程为子进程设置用户页错误入口。
  5. 子进程已经准备好运行了,有父进程将其标记为可运行。

每一次环境尝试向一个还不可写的写时复制的页面写入时,将出现页错误,用户页错误处理程序的控制流为:

  1. 内核将页错误传递给页错误上行调用,即调用了fork()的页错误处理程序。
  2. pgfault()检查错误为写入导致并且相应页面的PTE被标记为写时复制,否则使内核恐慌。
  3. pgfault()分配一个新的页面,映射至一个临时位置,然后复制错误页面的内容到新分配的页面,最后将新页面以读写权限映射到合适的地址,替代旧的只读页。

用户级别的lib/fork.c代码必须查询环境的页表(如查询某页面的PTE被标记为写时复制)。内核将环境的页表映射在UVPT正是为了这个目的。内核通过将页目录的指针指向自己的映射技巧使得可以为用户代码快速查找PTEs,lib/entry.S已经设置了uvpduvpd,你可以快速在lib/fork.c中查找页表信息。

练习12中遇到的问题:

  • 注意在pgfault()duppage()中,必须使用0而不是thisenv->env_id,原因已经在代码注释中标出
  • fork()中需要显式地判断用户异常页并跳过duppage()
  • 阅读给出的uvpt技巧,需要在代码中使用
  • 为了简化错误处理,避免重复代码,使用了goto
  • 假定先将父进程的用户栈标记为COW,然后再尝试将子进程的用户栈标记为COW之前,可能会出现父进程的用户栈已经被写入的情况而触发缺页错误,因此fork()会立刻分配新页,拷贝内容并重新映射。子进程被标记COW时复制的页映射已经不是原来的页映射了,因此,后来对父进程做的改动会反映在子进程上,这显然是错误的
  • fork后必须修改thisenv的值以保证用户程序行为正确

练习12的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
// In lib/fork.c, fork():
//
// User-level fork with copy-on-write.
// Set up our page fault handler appropriately.
// Create a child.
// Copy our address space and page fault handler setup to the child.
// Then mark the child as runnable and return.
//
// Returns: child's envid to the parent, 0 to the child, < 0 on error.
// It is also OK to panic on error.
//
// Hint:
// Use uvpd, uvpt, and duppage.
// Remember to fix "thisenv" in the child process.
// Neither user exception stack should ever be marked copy-on-write,
// so you must allocate a new page for the child's user exception stack.
//
envid_t fork(void) {
// LAB 4: Your code here.
int r;

// use set_pgfault_handler to install pgfault() as page fault handler
set_pgfault_handler(pgfault);

// use system call to create new blank child environment
envid_t child_env_id = sys_exofork();
if (child_env_id == 0) {
// must update thisenv to make sure user program behave
// normally
thisenv = envs + ENVX(sys_getenvid());
}
if (child_env_id < 0) {
// error when create new environment, simply return
return child_env_id;
}

// traverse through parent's address space and use duppage
// to copy address mappings
uintptr_t addr;
for (addr = 0; addr < UTOP; addr += PGSIZE) {
if ((((pde_t *)uvpd)[PDX(addr)] & PTE_P) &&
(((pte_t *)uvpt)[PGNUM(addr)] & PTE_P)) {
// if both page directory entry and page table entry
// exist for one address(page-aligned), then call duppage
if (addr == (UXSTACKTOP - PGSIZE)) {
// ignore user exception stack
// for we will map a page for user exception later
continue;
}
if ((r = duppage(child_env_id, PGNUM(addr))) < 0) {
// duppage failed
// destroy child environment and return
goto error_handle;
}
}
}

// child must have its own exception stack
// so alloc page and map it for child here
if ((r = sys_page_alloc(child_env_id, (void *)(UXSTACKTOP - PGSIZE),
PTE_P | PTE_U | PTE_W)) < 0) {
// failed to set child environment's exception stack
// destroy child environment and return
goto error_handle;
}

// set child's page fault handler so that parent
// and child looks the same
// use sys_env_set_pgfault_upcall system call
extern void _pgfault_upcall(void);
if ((r = sys_env_set_pgfault_upcall(child_env_id, _pgfault_upcall)) < 0) {
// failed to set child's page fault upcall
// destroy child environment and return
goto error_handle;
}

// now child is ready to run, set child to ENV_RUNNABLE
// use sys_env_set_status system call
if ((r = sys_env_set_status(child_env_id, ENV_RUNNABLE)) < 0) {
// failed to change child environment's running status
// destroy child environment and return
goto error_handle;
}

// panic("fork not implemented");

return child_env_id;

// use goto to avoid meaningless error_handle code
// copy and paste everywhere
error_handle:
if (sys_env_destroy(child_env_id) < 0) {
// failed either, panic then
panic("failed to destroy child environment!");
}
return r;
}

// In lib/fork.c, duppage():
//
// Map our virtual page pn (address pn*PGSIZE) into the target envid
// at the same virtual address. If the page is writable or copy-on-write,
// the new mapping must be created copy-on-write, and then our mapping must be
// marked copy-on-write as well. (Exercise: Why do we need to mark ours
// copy-on-write again if it was already copy-on-write at the beginning of
// this function?)
//
// Returns: 0 on success, < 0 on error.
// It is also OK to panic on error.
//
static int duppage(envid_t envid, unsigned pn) {
int r;

// LAB 4: Your code here.
int perm = PTE_P | PTE_U;
if ((((pte_t *)uvpt)[pn] & (PTE_W | PTE_COW))) {
// check for writable or copy-on-write page
// and add perm with PTE_COW
perm |= PTE_COW;
// NB: we also use 0 to replace thisenv->env_id
// for in unix-like fork() implementation, we will copy
// address space from parent process to child process
// at current time, thisenv->env_id IS ABSOLUTELY WRONG

// map from parent environment to child environment
if (sys_page_map(0, (void *)(pn * PGSIZE), envid, (void *)(pn * PGSIZE),
perm) < 0) {
panic("failed to map page from parent to child!");
}
// remap parent's environment
if (sys_page_map(0, (void *)(pn * PGSIZE), 0, (void *)(pn * PGSIZE),
perm) < 0) {
panic("failed to remap page in parent!");
}
} else {
// for other pages, simply map from
// parent environment to child environment
if (sys_page_map(0, (void *)(pn * PGSIZE), envid, (void *)(pn * PGSIZE),
perm) < 0) {
panic("failed to map page from parent to child!");
}
}

// panic("duppage not implemented");

return 0;
}

// In lib/fork.c, pgfault():
//
// Custom page fault handler - if faulting page is copy-on-write,
// map in our own private writable copy.
//
static void pgfault(struct UTrapframe *utf) {
void * addr = (void *)utf->utf_fault_va;
uint32_t err = utf->utf_err;
int r;

// Check that the faulting access was (1) a write, and (2) to a
// copy-on-write page. If not, panic.
// Hint:
// Use the read-only page table mappings at uvpt
// (see <inc/memlayout.h>).

// LAB 4: Your code here.
// use uvpt to get PTE and check premissions
if (!(err & FEC_WR) || !(((pte_t *)uvpt)[PGNUM(addr)] & PTE_COW)) {
panic("fault isn't write or PTE is not marked as PTE_COW or both!");
}

// Allocate a new page, map it at a temporary location (PFTEMP),
// copy the data from the old page to the new page, then move the new
// page to the old page's address.
// Hint:
// You should make three system calls.

// LAB 4: Your code here.
// allocate a page and map it at PFTEMP
// use sys_page_alloc system call
// NB: use 0 instead of thisenv->env_id
// for normally when child environment scheduled by JOS
// first it tries to store 0(return value of fork()) to
// local variable child_env_id on the stack
// which will take a page fault and kernel will trasfer control
// to pgfault here
// thisenv->env_id IS ABSOLUTELY WRONG here, so use 0
// and let kernel convert from 0 to correct env_id
if ((r = sys_page_alloc(0, (void *)PFTEMP, PTE_P | PTE_U | PTE_W)) < 0) {
panic("failed to allocate page at temp location - %e, %x!", r,
thisenv->env_id);
}

addr = ROUNDDOWN(addr, PGSIZE);
// use memcpy to copy from fault address's page to PFTEMP's newly
// allocated page
memcpy((void *)PFTEMP, addr, PGSIZE);

// use sys_page_map system call to map newly allocated
// page at PFTEMP at addr with read/write permissions
if ((r = sys_page_map(0, (void *)PFTEMP, 0, addr, PTE_P | PTE_U | PTE_W)) <
0) {
panic("failed to map new page - %e!", r);
}
// use sys_page_unmap system call to unmap page at
// temp location PFTEMP
if ((r = sys_page_unmap(0, (void *)PFTEMP)) < 0) {
panic("failed to unmap page at PFTEMP - %e!", r);
}

// panic("pgfault not implemented");
}

第三部分 - Preemptive Multitasking and Inter-Process communication (IPC) 抢占式多任务和进程间通信

最后一部分要求你修改内核,实现抢占式非协作环境以及允许环境显式传递信息。

时钟中断和抢占

运行user/spin测试程序,该测试程序fork一个用户环境,生成的子环境一旦获得了CPU,就会执行一个无限循环,无论是父环境还是内核都无法重新获得CPU。
对于从错误和恶意代码中保护系统而言,这不是一个理想的情况,因为任何用户环境都可以通过一个无限循环以及永不放弃使得整个系统停机。为了允许内核抢占一个用户环境并强制从该环境处获取CPU的控制,需要扩展JOS内核以支持时钟硬件的外部硬件中断。

中断规则

外部中断(如设备中断)被称为IRQs(Interrupt request)。总共有16种可能的IRQs,分别从0编号到15。从IRQ号到IDT入口的映射并不固定。picirq.c中的pic_init()将IRQs从0到15映射到了IRQ_OFFSET到IRQ_OFFSET + 15。

inc/trap.h中,IRQ_OFFSET被定义为32,因此IDT入口32-47对应于IRQ的0-15。例如,始终中断是IRQ 0。因此,IDT[IRQ_OFFSET + 0]包含了内核中时钟中断处理程序的地址。IRQ_OFFSET设置为32后,设备中断将不会和处理器异常号重叠。

同xv6 Unix相比,JOS内核提供了一个关键性简化。在内核中时,外部设备中断永远是被禁止的(但是在用户环境中是被允许的)。外部中断被%eflags寄存器的FL_IF标记控制。当该bit被设置时,外部中断被允许。尽管有若干种方式可以修改该bit位,将在进入和退出用户模式时通过保存和恢复%eflags寄存器的过程来处理它。

必须确保在用户环境中FL_IF标记被设置,这样当中断到达后,并且将中断传递给处理器,并由内核中的中断处理程序处理。否则中断会被屏蔽和忽略之道中断重新被允许。在引导程序的第一条指定就屏蔽了外部设备中断,并且直到目前为止,还没有重新启用。

练习13中遇到的问题:

  • 注意到简化规则要求中说明必须在陷入内核时将IF置0,所以必须修改之前的代码,将所有门都改为中断门

练习13的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// In kern/trapentry.S:
// externel interrupts
TRAPHANDLER_NOEC(irq_0_handler, IRQ_OFFSET + 0);
TRAPHANDLER_NOEC(irq_1_handler, IRQ_OFFSET + 1);
TRAPHANDLER_NOEC(irq_2_handler, IRQ_OFFSET + 2);
TRAPHANDLER_NOEC(irq_3_handler, IRQ_OFFSET + 3);
TRAPHANDLER_NOEC(irq_4_handler, IRQ_OFFSET + 4);
TRAPHANDLER_NOEC(irq_5_handler, IRQ_OFFSET + 5);
TRAPHANDLER_NOEC(irq_6_handler, IRQ_OFFSET + 6);
TRAPHANDLER_NOEC(irq_7_handler, IRQ_OFFSET + 7);
TRAPHANDLER_NOEC(irq_8_handler, IRQ_OFFSET + 8);
TRAPHANDLER_NOEC(irq_9_handler, IRQ_OFFSET + 9);
TRAPHANDLER_NOEC(irq_10_handler, IRQ_OFFSET + 10);
TRAPHANDLER_NOEC(irq_11_handler, IRQ_OFFSET + 11);
TRAPHANDLER_NOEC(irq_12_handler, IRQ_OFFSET + 12);
TRAPHANDLER_NOEC(irq_13_handler, IRQ_OFFSET + 13);
TRAPHANDLER_NOEC(irq_14_handler, IRQ_OFFSET + 14);
TRAPHANDLER_NOEC(irq_15_handler, IRQ_OFFSET + 15);

// In kern/trap.c, trap_init():
// set up interupt gate descriptor
SETGATE(idt[IRQ_OFFSET + 0], 0, GD_KT, irq_0_handler, 0);
SETGATE(idt[IRQ_OFFSET + 1], 0, GD_KT, irq_1_handler, 0);
SETGATE(idt[IRQ_OFFSET + 2], 0, GD_KT, irq_2_handler, 0);
SETGATE(idt[IRQ_OFFSET + 3], 0, GD_KT, irq_3_handler, 0);
SETGATE(idt[IRQ_OFFSET + 4], 0, GD_KT, irq_4_handler, 0);
SETGATE(idt[IRQ_OFFSET + 5], 0, GD_KT, irq_5_handler, 0);
SETGATE(idt[IRQ_OFFSET + 6], 0, GD_KT, irq_6_handler, 0);
SETGATE(idt[IRQ_OFFSET + 7], 0, GD_KT, irq_7_handler, 0);
SETGATE(idt[IRQ_OFFSET + 8], 0, GD_KT, irq_8_handler, 0);
SETGATE(idt[IRQ_OFFSET + 9], 0, GD_KT, irq_9_handler, 0);
SETGATE(idt[IRQ_OFFSET + 10], 0, GD_KT, irq_10_handler, 0);
SETGATE(idt[IRQ_OFFSET + 11], 0, GD_KT, irq_11_handler, 0);
SETGATE(idt[IRQ_OFFSET + 12], 0, GD_KT, irq_12_handler, 0);
SETGATE(idt[IRQ_OFFSET + 13], 0, GD_KT, irq_13_handler, 0);
SETGATE(idt[IRQ_OFFSET + 14], 0, GD_KT, irq_14_handler, 0);
SETGATE(idt[IRQ_OFFSET + 15], 0, GD_KT, irq_15_handler, 0);

// In kern/env.c, env_alloc():
// Enable interrupts while in user mode.
// LAB 4: Your code here.
// simply use bit or to set FL_IF
e->env_tf.tf_eflags |= FL_IF;

// In kern/sched.c, sched_halt():
// Reset stack pointer, enable interrupts and then halt.
asm volatile (
"movl $0, %%ebp\n"
"movl %0, %%esp\n"
"pushl $0\n"
"pushl $0\n"
// Uncomment the following line after completing exercise 13
"sti\n"
"1:\n"
"hlt\n"
"jmp 1b\n"
: : "a" (thiscpu->cpu_ts.ts_esp0));

处理时钟中断

user/spin程序中,在子环境第一次运行后,会陷入无限循环,而内核将无法得到控制权,需要对硬件编程以定时产生时钟中断,该终端会将控制权强行切回CPU,然后可以将控制权交给另一个用户环境。

对于lapic_init()pic_init()的调用已经写好,它们会设置时钟并且终端控制器会定时生成中断。需要完成代码处理这些中断。

练习14中遇到的问题:

  • 首先需要调用lapic_eoi()以确认接收到了中断,否则会一直卡住

练习14的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
// in kern/trap.c, trap_dispatch():
// new code added
if (tf->tf_trapno == IRQ_OFFSET + IRQ_TIMER) {
// dispatch clock interupts
// call sched_yield() to find and run a different environment
// NB: should first call lapic_eoi() to ACKNOWLEDGE interupt
lapic_eoi();
sched_yield();
// sched_yield() might not return
}

进程间通讯

到目前位置实验一直关注于操作系统的独立部分,操作系统通过虚拟化提供了一种每个环境都独占整个机器的“错觉”。然而操作系统的另一项服务是允许程序在必要的时候通讯,该功能非常强大,Unix管道就是一个典型的例子。

有许多进程间通讯的模型,即使是现在也有许多关于哪一种模型是最好的争论。我们不参与争论。相反,我们将实现一个简单的IPC模型。

JOS中的IPC

你将实现一些额外的JOS内核系统调用,这些调用共同提供一个简单的进程间通讯机制。具体的系统调用为sys_ipc_recv()sys_ipc_try_send(),然后你将实现两个库包装ipc_recv()ipc_send()

用户环境通过JOS的IPC机制向其他环境互相发送的信息包括两部分,一个32-bit的值和一个可选的单页映射。允许环境传递页映射提供了一个比传递一个32-bit的整数更有效的数据交换方式,这也可以较为方便的设置共享内存。

发送和接收消息

环境调用sys_ipc_recv()去接受消息。该系统调用取消调度当前环境并且直到一条消息被收到后才会被继续运行。当一个环境等待接收消息时,任何其他的环境可以向其发送一条消息 - 并不限于特定的环境,也不限于父子进程间传递消息,换言之,你在第一部分中实现的权限检查将不适用于IPC,因为IPC系统调用经过精心设计以保证安全,环境不会通过简单地发送消息而导致其他环境出现错误(除非目标环境也有错误)。

环境调用sys_ipc_try_send()去尝试发送一个值(并附带上接受者的环境ID),如果指定的环境实际上正在接受该值(已调用sys_ipc_recv()并且尚未获得值),则值成功发送并返回0。否则,返回-E_IPC_NOT_RECV表示目标环境当前不期望接收值。

用户空间的库函数ipc_recv()将负责调用sys_ipc_recv()并在当前环境的struct Env中查找接收值的信息。

用户空间的库函数ipc_send()将负责反复调用sys_ipc_try_send()直到发送成功。

传输页

当一个环境以一个有效的dstva参数(小于UTOP)调用sys_ipc_recv()时,环境改变状态以表明想要接受一个页映射。如果发送者发送了一个页,那么该页将会被映射到接收者地址空间的dstva处。如果接收者已经在dstva映射了一页,那么之前的页会被解映射。

当一个环境以一个有效的srcva参数(小于UTOP)调用sys_ipc_try_send()时,表明发送者想要将当前映射在srcva的页发送给接收者,并且带有权限perm。在一次成功的IPC之后,发送者在其地址空间保留在srcva处原有的页映射,但是接收者也持有最开始由发送者指定的相同的物理页面在dstva的映射。最终,该页面在发送者和接收者之间共享。

如果发送者和接收者两者之一没有表明要传输页面,那么将不会有页面被传输。在任意一次IPC之后将接收者的struct Env中新的域env_ipc_perm设置为接受页面的权限,如果没有收到页面,则为0。

实现IPC

练习15中遇到的问题:

  • sys_ipc_try_send()sys_ipc_recv()中,均不将超过UTOP的地址标记为错误,超过UTOP的地址是无效的,但并不会导致系统调用失败
  • sys_ipc_recv()中在接收到消息前将环境状态置为不可运行,那么在收到消息后,应当恢复到可运行的状态
  • sys_ipc_try_send()中调用page_lookup()时,要记住检查的是源地址的映射,因此应当使用当前环境的页表而非接收者环境的页表

练习15的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
// In kern/syscall.c, sys_ipc_recv():
// Block until a value is ready. Record that you want to receive
// using the env_ipc_recving and env_ipc_dstva fields of struct Env,
// mark yourself not runnable, and then give up the CPU.
//
// If 'dstva' is < UTOP, then you are willing to receive a page of data.
// 'dstva' is the virtual address at which the sent page should be mapped.
//
// This function only returns on error, but the system call will eventually
// return 0 on success.
// Return < 0 on error. Errors are:
// -E_INVAL if dstva < UTOP but dstva is not page-aligned.
static int sys_ipc_recv(void *dstva) {
// LAB 4: Your code here.
// similar to sys_ipc_try_send, will not mark an error
// if dstva >= UTOP
if ((uintptr_t)dstva < UTOP && PGOFF(dstva) != 0) {
// if dstva < UTOP but dstva is not page-aligned
// NB: && rather than ||, we won't report error
// when dstva >= UTOP
return -E_INVAL;
}

// mark calling environment as not runnable
curenv->env_status = ENV_NOT_RUNNABLE;
// update status to mark receiver is willing to receive message
curenv->env_ipc_recving = true;
curenv->env_ipc_dstva = dstva;

// give up cpu
sys_yield();

// panic("sys_ipc_recv not implemented");

// ipc succeeds
return 0;
}

// In kern/syscall.c, sys_ipc_try_send():
// Try to send 'value' to the target env 'envid'.
// If srcva < UTOP, then also send page currently mapped at 'srcva',
// so that receiver gets a duplicate mapping of the same page.
//
// The send fails with a return value of -E_IPC_NOT_RECV if the
// target is not blocked, waiting for an IPC.
//
// The send also can fail for the other reasons listed below.
//
// Otherwise, the send succeeds, and the target's ipc fields are
// updated as follows:
// env_ipc_recving is set to 0 to block future sends;
// env_ipc_from is set to the sending envid;
// env_ipc_value is set to the 'value' parameter;
// env_ipc_perm is set to 'perm' if a page was transferred, 0 otherwise.
// The target environment is marked runnable again, returning 0
// from the paused sys_ipc_recv system call. (Hint: does the
// sys_ipc_recv function ever actually return?)
//
// If the sender wants to send a page but the receiver isn't asking for one,
// then no page mapping is transferred, but no error occurs.
// The ipc only happens when no errors occur.
//
// Returns 0 on success, < 0 on error.
// Errors are:
// -E_BAD_ENV if environment envid doesn't currently exist.
// (No need to check permissions.)
// -E_IPC_NOT_RECV if envid is not currently blocked in sys_ipc_recv,
// or another environment managed to send first.
// -E_INVAL if srcva < UTOP but srcva is not page-aligned.
// -E_INVAL if srcva < UTOP and perm is inappropriate
// (see sys_page_alloc).
// -E_INVAL if srcva < UTOP but srcva is not mapped in the caller's
// address space.
// -E_INVAL if (perm & PTE_W), but srcva is read-only in the
// current environment's address space.
// -E_NO_MEM if there's not enough memory to map srcva in envid's
// address space.
static int sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva,
unsigned perm) {
// LAB 4: Your code here.
// check for existence of env with envid
struct Env *env;
if (envid2env(envid, &env, false) < 0) {
// environment envid doesn't currently exist
return -E_BAD_ENV;
}

// check receiver's status
if (!env->env_ipc_recving) {
// envid is not currently blocked in sys_ipc_recv
// or another environment managed to send first
return -E_IPC_NOT_RECV;
}

if ((uintptr_t)srcva < UTOP) {
// srcva is valid
// check srcva is page-aligned
if (PGOFF(srcva) != 0) {
// srcva is not page-aligned
return -E_INVAL;
}
// check perm passed in
if ((perm & (~PTE_SYSCALL)) || !(perm & PTE_U) || !(perm & PTE_P)) {
// invalid perm
return -E_INVAL;
}
// check srcva actually be mapped
pte_t * pgtable_entry;
struct PageInfo *page;
if ((page = page_lookup(curenv->env_pgdir, srcva, &pgtable_entry)) ==
NULL) {
// NB: check for SRCVA here, so use curenv->env_pgdir
// srcva is not mapped at caller's address space
return -E_INVAL;
}
// check PTE_W between sender and receiver
if ((perm & PTE_W) && (!((*pgtable_entry) & PTE_W))) {
// if perm has PTE_W while srcva is read-only in
// current environment's address space
return -E_INVAL;
}

if ((uintptr_t)(env->env_ipc_dstva) < UTOP) {
// receiver also expects page to be transferred
// call page_insert to actually transer the page
if (page_insert(env->env_pgdir, page, env->env_ipc_dstva, perm) <
0) {
// out of memory when try to insert page
return -E_NO_MEM;
}
// page successfully transferred
env->env_ipc_perm = perm;
}
} else {
// srcva >= UTOP
// invalid srcva, but we won't return error here
// ipc_send will panic if we do so
}

// update receiver's information
env->env_ipc_recving = false;
env->env_ipc_from = curenv->env_id;
env->env_ipc_value = value;
// mark receiver to be runnable to match what we do in sys_ipc_recv
env->env_status = ENV_RUNNABLE;
// modify trapframe's eax register to `update' return value
env->env_tf.tf_regs.reg_eax = 0;

// panic("sys_ipc_try_send not implemented");

// ipc succeeds
return 0;
}

// In lib/ipc.c, ipc_recv():
// Receive a value via IPC and return it.
// If 'pg' is nonnull, then any page sent by the sender will be mapped at
// that address.
// If 'from_env_store' is nonnull, then store the IPC sender's envid in
// *from_env_store.
// If 'perm_store' is nonnull, then store the IPC sender's page permission
// in *perm_store (this is nonzero if a page was successfully
// transferred to 'pg').
// If the system call fails, then store 0 in *fromenv and *perm (if
// they're nonnull) and return the error.
// Otherwise, return the value sent by the sender
//
// Hint:
// Use 'thisenv' to discover the value and who sent it.
// If 'pg' is null, pass sys_ipc_recv a value that it will understand
// as meaning "no page". (Zero is not the right value, since that's
// a perfectly valid place to map a page.)
int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store) {
// LAB 4: Your code here.
// check pg, if pg is null, then should set it to UTOP,
// for only if dstva is below UTOP, sender knows that
// receiver wants a page to be transferred
if (!pg) { pg = (void *)UTOP; }
int r;
if ((r = sys_ipc_recv(pg)) < 0) {
// system call fails
// store from env and perm if corresponding pointer is not null
if (from_env_store) { *from_env_store = 0; }
if (perm_store) { *perm_store = 0; }
// return the error
return r;
}

// system call succeeds
// extract information from thisenv's IPC fields
if (from_env_store) {
// store IPC sender's envid into *from_env_store
*from_env_store = thisenv->env_ipc_from;
}
if (perm_store) {
// store IPC sender's page permission
*perm_store = thisenv->env_ipc_perm;
}

// panic("ipc_recv not implemented");

// return the value send by the sender
return thisenv->env_ipc_value;
}

// In kern/syscall.c, syscall():
// new code added
case SYS_ipc_recv:
// call sys_ipc_recv
return sys_ipc_recv((void *)a1);
break;
case SYS_ipc_try_send:
// call sys_ipc_try_send
return sys_ipc_try_send((envid_t)a1, (uint32_t)a2, (void *)a3,
(unsigned)a4);

// In lib/ipc.c, ipc_send():
// Send 'val' (and 'pg' with 'perm', if 'pg' is nonnull) to 'toenv'.
// This function keeps trying until it succeeds.
// It should panic() on any error other than -E_IPC_NOT_RECV.
//
// Hint:
// Use sys_yield() to be CPU-friendly.
// If 'pg' is null, pass sys_ipc_try_send a value that it will understand
// as meaning "no page". (Zero is not the right value.)
void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm) {
// LAB 4: Your code here.
// check pg, if pg is null, then should set it to UTOP(invalid value
// but won't result in panic)
if (!pg) { pg = (void *)UTOP; }
int r;
while (true) {
// keeps trying until succeeds or panic
r = sys_ipc_try_send(to_env, val, pg, perm);
if (r == 0) {
// message successfully sent, return
return;
}
if (r != -E_IPC_NOT_RECV) {
// error when sending, should panic
panic("failed to send messages - %e!", r);
}
// use sys_yield to avoid waste on CPU
sys_yield();
}

// panic("ipc_send not implemented");
}

实验小结

最终执行make grade,评分脚本的输出如下:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
dumbfork:
$ make run-dumbfork-nox-gdb QEMUEXTRA+=-snapshot
OK (1.6s)
Part A score: 5/5
faultread:
$ make run-faultread-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
faultwrite:
$ make run-faultwrite-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
faultdie:
$ make run-faultdie-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
faultregs:
$ make run-faultregs-nox-gdb QEMUEXTRA+=-snapshot
OK (1.1s)
faultalloc:
$ make run-faultalloc-nox-gdb QEMUEXTRA+=-snapshot
OK (4.6s)
faultallocbad:
$ make run-faultallocbad-nox-gdb QEMUEXTRA+=-snapshot
OK (1.3s)
faultnostack:
$ make run-faultnostack-nox-gdb QEMUEXTRA+=-snapshot
OK (1.8s)
faultbadhandler:
$ make run-faultbadhandler-nox-gdb QEMUEXTRA+=-snapshot
OK (1.2s)
faultevilhandler:
$ make run-faultevilhandler-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
forktree:
$ make run-forktree-nox-gdb QEMUEXTRA+=-snapshot
OK (1.4s)
Part B score: 50/50
spin:
$ make run-spin-nox-gdb QEMUEXTRA+=-snapshot
OK (0.7s)
stresssched:
$ make run-stresssched-nox-gdb CPUS=4 QEMUEXTRA+=-snapshot
OK (3.0s)
sendpage:
$ make run-sendpage-nox-gdb CPUS=2 QEMUEXTRA+=-snapshot
OK (1.7s)
pingpong:
$ make run-pingpong-nox-gdb CPUS=4 QEMUEXTRA+=-snapshot
OK (2.1s)
primes:
$ make run-primes-nox-gdb CPUS=4 QEMUEXTRA+=-snapshot
OK (4.5s)
Part C score: 25/25
Score: 80/80

至此,实验四结束。

第四个实验是第一到第四个实验中难度最大、代码量最多的一个实验,在前三个实验中任何的代码错误(尽管可能在当时的实验评分中没有反映出来)都会导致实验四出现难以调试的错误。

实验四中每个练习遇到的问题我都已经在报告中总结,此外,也在代码中以NB标明。其中大部分都是一些小错误,还有少部分是没有将问题考虑全面导致的。尽管如此,几乎每一个错误我都花费了至少几十分钟去调试。

操作系统的调试不仅仅困难(Triple Fault会导致不打补丁的qemu重启),任何一个小错误都会导致系统崩溃。现代操作系统如Linux的鲁棒性可见一斑。

本学期的事情比起上学期只增不减,加上课程设计只要求完成四个实验,实验四结束后,MIT-6.828系列就告一段落了。

希望我的这四篇实验报告能对正在写实验的你产生些许的启发,也欢迎找我交流相关的问题。

评论和共享

Lab3 - User Environments需要实现基本的内核功能,使得一个受保护的用户环境(进程)可以运行。在本实验中,需要让内核设置数据结构以追踪用户环境,创建一个单用户环境,加载程序镜像并执行。此外,内核还需要能处理用户环境的系统调用以及引发的异常。
2018年2月26日,完成了实验并写完了报告。

实验准备

根据官网,切换到分支lab3并且合并分支lab2。在合并的过程中,发生了冲突。

1
2
user% git checkout -b lab3 origin/lab3
user% git merge lab2

根据提示,是kern/monitor.c中发生了冲突,因为仅有一处冲突,手动编辑kern/monitor.c文件,并commit,即可解决冲突并合并分支。

实验三包括如下的新文件:

  • inc/env.h 用户模式环境的公有定义
  • inc/trap.h 陷阱处理的公有定义
  • inc/syscall.h 用户环境对内核的系统调用的公有定义
  • inc/lib.h 用户模式支持的库公有定义
  • kern/env.h 用户模式环境的内核私有定义
  • kern/env.c 用户模式环境的内核代码实现
  • kern/trap.h 内核私有的陷阱处理定义
  • kern/trap.c 陷阱处理代码
  • kern/trapentry.S 汇编语言的陷阱处理程序入口
  • kern/syscall.h 系统调用处理的内核私有定义
  • kern/syscall.c 系统调用实现代码
  • lib/Makefrag 用户模式库obj/lib/libjos.a的Makefile
  • lib/entry.S 用户环境的汇编语言入口
  • lib/libmain.c entry.S调用的用户模式库安装代码
  • lib/syscall.c 用户模式系统调用的打桩函数
  • lib/console.c 用户模式的putchar和getchar实现,提供了控制台IO
  • lib/exit.c 用户模式的exit实现
  • lib/panic.c 用户模式的panic实现
  • user/* 检验内核实验三代码的测试程序

此外,lab2中的一些文件在lab3中也被添加了新的内容,可以用git diff lab2查看具体的比较信息。

内联汇编

本实验中可能会用到GCC的内联汇编特性,应当至少理解给出的代码中的内联汇编代码片段。

实验过程

第一部分 User Environments and Exception Handling - 用户环境和错误处理

inc/env.h中给出了用户环境的基本定义。内核通过struct Env追踪每一个用户环境。本实验中只需要创建一个环境,然而你需要设计JOS内核实际支持多用户环境。实验四中,你将通过允许一个用户环境fork别的用户环境来利用多用户环境的特性。

kern/env.c中可以看到,内核管理3个与环境有关的全局变量:

1
2
3
struct Env *       envs   = NULL;    // All environments
struct Env * curenv = NULL; // The current env
static struct Env *env_free_list; // Free environment list

当JOS成功运行之后,envs指针指向一个struct Env的数组,代表了系统中所有的环境。在设计上,JOS内核允许NNEV个同时激活的环境,NNEV在inc/env.h中定义。
JOS内核使用env_free_list维护所有未激活的struct Env,这样的设计简化的环境的分配和释放,它们仅仅需要从该链表上添加或移除。
JOS内核使用curenv去追踪在任意时刻当前正在执行的环境。在启动之后到第一个环境运行的时间段中,curenv被初始化为NULL

环境状态

struct Envinc/env.h中被定义:

1
2
3
4
5
6
7
8
9
10
11
12
struct Env {
struct Trapframe env_tf; // Saved registers
struct Env *env_link; // Next free Env
envid_t env_id; // Unique environment identifier
envid_t env_parent_id; // env_id of this env's parent
enum EnvType env_type; // Indicates special system environments
unsigned env_status; // Status of the environment
uint32_t env_runs; // Number of times environment has run

// Address space
pde_t *env_pgdir; // Kernel virtual address of page dir
};

  • env_tf - struct TrapFrameinc/trap.h中被定义,表示了当环境不运行时被保存的寄存器值,主要用于上下文切换
  • env_link - 指向了env_free_list上的下一个struct Envenv_free_list指向了链表中的第一个空闲环境
  • env_id - 唯一标识当前正在使用struct Env的环境。当环境终止后,struct Env可能被内核重新分配用于另一个不同的环境,但它们的env_id是不同的
  • env_parent_id - 存储了创建该环境的环境的env_id,通过该方式构建一个环境树,用于安全方面的决策
  • env_type - 用于区分特殊环境,对于大部分环境,该值为ENV_TYPE_USER,在后续Lab中会介绍其他的值
  • env_status - 状态
    • ENV_FREE - 表明struct Env处于空闲状态,应当位于env_free_list
    • ENV_RUNNABLE - 表明struct Env代表的环境正等待运行于处理器上
    • ENV_RUNNING - 表明struct Env代表的环境为正在运行的环境
    • ENV_NOT_RUNNABLE - 表明struct Env代表了一个正在运行的环境,但却没有准备好运行,如正在等待另一个环境的IPC(进程间通信)
    • ENV_DYING - 表明struct Env代表了一个僵死环境,僵死环境将在下一次陷入内核时被释放(直到Lab4才会使用该Flag)
  • env_pgdir - 保存了环境的页目录的内核虚拟地址

JOS中环境的概念综合了“线程”和“地址空间”,“线程”由env_tf域的被保存的寄存器值定义,“地址空间”由env_pgdir域指向的页目录和页表定义。为了运行一个环境,内核必须用保存的寄存器值和合适的地址空间设置CPU。

JOS的struct Env和xv6的struct proc很像,两种结构体都持有环境的用户模式寄存器状态(通过struct TrapFrame),然而,JOS中,独立的环境并不具有不同的内核栈,因为JOS内核中同时只能有一个运行的JOS环境,因此JOS只需要一个内核栈。

分配环境数组

练习1的代码如下,仅供参考:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//////////////////////////////////////////////////////////////////////
// Make 'envs' point to an array of size 'NENV' of 'struct Env'.
// LAB 3: Your code here.
// get size of envs
uint32_t envs_size = sizeof(struct Env) * NENV;
// use boot_alloc to allocate memory
envs = (struct Env *)boot_alloc(envs_size);
// initialization
memset(envs, 0, envs_size);

//////////////////////////////////////////////////////////////////////
// Map the 'envs' array read-only by the user at linear address UENVS
// (ie. perm = PTE_U | PTE_P).
// Permissions:
// - the new image at UENVS -- kernel R, user R
// - envs itself -- kernel RW, user NONE
// LAB 3: Your code here.
boot_map_region(kern_pgdir, UENVS, envs_size, PADDR(envs), PTE_U | PTE_P);

创建并运行环境

现在将在kern/env.c中编写必要的代码去运行用户环境。由于JOS内核还不支持文件系统,所以只能配置内核以加载一个嵌入内核中静态二进制镜像。JOS内核将这个二进制镜像以ELF可执行镜像格式嵌入。

Lab3的GNUMakefileobj/user/目录下生成了一些二进制镜像。kern/Makefrag下可以看到,链接器的-b binary选项使得这些文件以原始的未被翻译二进制文件而非普通的被编译器生成的.o文件的方式链接, 通过-b binary方式链接的二进制文件就链接器而言可以为任意类型,甚至是文本文件或是图片。

如果在构建内核后观察obj/kern/kernel.sym,可以看到链接器生成了一些“奇怪”名字的符号如_binary_obj_user_hello_start_binary_obj_user_hello_end_binary_obj_user_hello_size。链接器通过二进制文件的名字生成了这些符号的名字,这些符号使得内核代码可以以某种方式引用这些嵌入的二进制文件。

练习2中遇到的问题:

  • 除了env->env_tf.tf_eip以外不要修改其他的值,因为其已经在env_alloc()中被初始化
  • region_alloc()中笔误导致只映射了一页
  • load_icode()中需要切换页表,之后加载每段仅用一个memcpy即可实现

练习2的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// In env_init():
// LAB 3: Your code here.
ssize_t i;
// loop in reverse order to keep ascending order in env free list
for (i = NENV - 1; i >= 0; i--) {
// set env_status, env_id
envs[i].env_status = ENV_FREE;
envs[i].env_id = 0;
// set env_link and insert into env_free_list
envs[i].env_link = env_free_list;
env_free_list = &envs[i];
}

// In env_setup_vm():
// LAB 3: Your code here.
// set env_pgdir and generate page directory based on kern_pgdir
e->env_pgdir = (pde_t *)page2kva(p);
memcpy(e->env_pgdir, kern_pgdir, PGSIZE);
// increase pp_ref
p->pp_ref++;

// In region_alloc():
// LAB 3: Your code here.
// (But only if you need it for load_icode.)
//
// Hint: It is easier to use region_alloc if the caller can pass
// 'va' and 'len' values that are not page-aligned.
// You should round va down, and round (va + len) up.
// (Watch out for corner-cases!)

// round va and va + len
uintptr_t start = (uintptr_t)ROUNDDOWN(va, PGSIZE);
uintptr_t end = (uintptr_t)ROUNDUP(va + len, PGSIZE);

for (; start < end; start += PGSIZE) {
// alloc page
struct PageInfo *p;
p = page_alloc(ALLOC_ZERO);
if (!p) { panic("out of memory when allocating region!"); }
// insert page into environment's page directory
if (page_insert(e->env_pgdir, p, (char *)start, PTE_W | PTE_U | PTE_P) <
0) {
panic("out of memory when allocating region!");
}
}

// In load_icode():
// LAB 3: Your code here.
// switch address space for loading program segments
lcr3(PADDR(e->env_pgdir));

struct Elf *elf = (struct Elf *)binary;
// check elf magic
if (elf->e_magic != ELF_MAGIC) { panic("invalid elf format!"); }

// set the program entry for env
e->env_tf.tf_eip = elf->e_entry;

struct Proghdr *ph, *eph;

// get the start and end of program header entry
ph = (struct Proghdr *)(binary + elf->e_phoff);
eph = ph + elf->e_phnum;
for (; ph < eph; ph++) {
if (ph->p_type == ELF_PROG_LOAD) { // if the segment is to be loaded
// alloc corresponding region(clear zero)
region_alloc(e, (char *)ph->p_va, ph->p_memsz);
// copy from ELF header to virtual addresses directly
memcpy((char *)ph->p_va, (char *)binary + ph->p_offset, ph->p_filesz);
}
}
// switch back
lcr3(PADDR(kern_pgdir));

// Now map one page for the program's initial stack
// at virtual address USTACKTOP - PGSIZE.
// LAB 3: Your code here.
// allocate a page and insert it into env's page directory
// panic when page_alloc or page_insert failed
struct PageInfo *stack_page = page_alloc(ALLOC_ZERO);
if (!stack_page) { panic("out of memory when alloc program's stack!"); }
if (page_insert(e->env_pgdir, stack_page, (char *)(USTACKTOP - PGSIZE),
PTE_W | PTE_U | PTE_P) < 0) {
panic("failed to set program's stack!");
}

// In env_create():
// LAB 3: Your code here.
struct Env *env;
// allocate new env with parent ID 0
if (env_alloc(&env, 0) < 0) { panic("failed to allocate env!"); }
// load elf binary and set env_type
load_icode(env, binary);
env->env_type = type;

// In env_run():
// LAB 3: Your code here.
if (curenv != NULL) { // context switch
if (curenv->env_status == ENV_RUNNING) {
// change to runnable if current status is running
// for not runnable, is not necessary to do this
curenv->env_status = ENV_RUNNABLE;
}
}

// set new curenv, update status and counter
curenv = e;
e->env_status = ENV_RUNNING;
e->env_runs++;
// address space switch
// reference from inc/x86.h
lcr3(PADDR(e->env_pgdir));
// drop into user mode
env_pop_tf(&(e->env_tf));

// panic("env_run not yet implemented");

成功进入用户环境后,若用户环境尝试使用int指令进行系统调用时,将产生错误,因为JOS没有设置任何从用户空间进入内核的方式。
当CPU发现无法处理系统中断调用后,会产生一个通用保护错误,发现无法处理它,然后生成一个二重错误,最终因无法处理而生成一个三重错误并放弃,然后系统重启。但是为了便于调试,patch的qemu不会重启。
关于重启的理由可以参考这里

完成后经过测试,程序在int $0x30处Triple Fault,可知本部分代码基本正确。

处理中断和异常

练习3要求阅读Intel 80386编程手册中的第九章:异常和中断

本实验中将沿用Intel关于中断和异常的术语。中断是由处理器以外的异步事件引发的,而异常是由当前正在执行的指令同步引发的。

保护控制转移基础

异常和中断均为“保护控制转移”,会引发处理器从用户到内核模式(CPL=0),从而避免给用户模式的代码干扰内核或是其他环境的机会。这要求了引发中断或者是异常的代码不能选择进入内核的地点或方式。
在x86中,主要有两种机制一起保证了内核总是在受保护的情况下进入,这两种机制为中断描述符表(Interrupt Descriptor Table)和任务状态段(Task State Segment)。

中断描述符表中,处理器保证了异常和中断仅能导致内核在若干个具体的、由内核明确定义好的入口执行,而不是在中断和异常发生时运行的代码。
x86允许最多设立256个不同的中断或异常入口,每一个入口都具有一个中断向量。中断向量为0-255的数字,中断向量由中断来源决定:不同的设备,错误条件和应用程序对内核的请求会产生不同向量的中断。CPU使用中断向量作为处理器的中断描述符表的索引。中断描述符表在内核私有的内存中建立。
处理器从该表中加载送入EIP寄存器的值(处理程序的入口),以及送入CS段寄存器的值(包括了特权级,在JOS中,所有的异常均在内核模式执行,即特权级0)。

任务状态段。处理器需要在唤醒处理程序前将在中断或异常发生前的旧的处理器状态保存起来,如旧的EIP寄存器值和旧的CS段寄存器值,以便处理程序之后能恢复现场,从中断或异常发生的地方继续执行。然而,保存旧的处理器状态的区域必须对于非特权的用户模式代码处于被保护的状态。否则,错误的或是恶意的用户代码可能会破坏内核。
因此,当x86处理器从用户模式特权级切换到内核模式时,其也会切换到内核内存中的一个栈。任务状态段指定了相应的段寄存器以及相应栈的地址。处理器将SS, EFLAGS, CS, EIP以及一个可选的错误码压入这个新栈中。然后从中断描述符中读取相应的CSEIP,并设置ESPSS指向新的栈。
尽管TSS有着多种作用,JOS仅用它来定义从用户模式切换到内核模式时的内核栈。因为JOS中的内核模式为x86的特权级0,故处理器仅使用TSSESP0SS0域。

异常和中断的类型

x86处理器能产生的所有同步异常均使用了0-31的中断向量,映射为IDT的0-31号入口。超过31的中断向量仅供由int指令或是由异步硬件中断产生的“软中断”使用。

嵌套异常和中断

处理器能同时处理内核模式和用户模式的异常。在内核模式中的异常不需要切换栈,因此,不需要压入旧的SSESP值。通过这种方式,内核可以优雅地处理内核产生的嵌套异常和中断。该能力对于实现保护是非常重要的。

若处理器已经在内核模式中并且接受了一个异常并且无法将旧值压入内核栈中时(如内存不足),那么,处理器将无论如何也无法恢复,只能重启。内核必须设计良好以避免这种情况发生。

建立IDT表

由于JOS中使用的为IA_32的陷阱码,更推荐参考IA_32的第五章

练习4中遇到的问题如下:

  • 设置陷阱门时段选择子应当为GD_KT而不是GD_KD,因为错误处理函数均被链接至了内核的text段。
  • 已存在page_fault_handler的函数,命名时需避免重名。
  • 不能直接用立即数设置段寄存器。

练习4的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// In trapentry.S:
/*
* Lab 3: Your code here for generating entry points for the different traps.
*/

TRAPHANDLER_NOEC(divide_error_handler, T_DIVIDE)
TRAPHANDLER_NOEC(debug_exception_handler, T_DEBUG)
TRAPHANDLER_NOEC(non_maskable_interrupt_handler, T_NMI)
TRAPHANDLER_NOEC(breakpoint_handler, T_BRKPT)
TRAPHANDLER_NOEC(overflow_handler, T_OFLOW)
TRAPHANDLER_NOEC(bounds_check_handler, T_BOUND)
TRAPHANDLER_NOEC(invalid_opcode_handler, T_ILLOP)
TRAPHANDLER_NOEC(device_not_available_handler, T_DEVICE)
TRAPHANDLER(double_fault_handler, T_DBLFLT)
TRAPHANDLER(invalid_tss_handler, T_TSS)
TRAPHANDLER(segment_not_present_handler, T_SEGNP)
TRAPHANDLER(stack_exception_handler, T_STACK)
TRAPHANDLER(general_protection_fault_handler, T_GPFLT)
TRAPHANDLER(pagefault_handler, T_PGFLT)
TRAPHANDLER_NOEC(floating_point_error_handler, T_FPERR)
TRAPHANDLER(alignment_check_handler, T_ALIGN)
TRAPHANDLER_NOEC(machine_check_handler, T_MCHK)
TRAPHANDLER_NOEC(simd_floating_point_error_handler, T_SIMDERR)

/*
* Lab 3: Your code here for _alltraps
*/

_alltraps:
// push ds and es and general registers
push %ds
push %es
pushal

// load ds and es with GD_KD, for kernel stack locates in data
mov $GD_KD, %ax
mov %ax, %ds
mov %ax, %es

// pass tf as an argument
pushl %esp

// call trap and no need to return
call trap

// In trap.c, trap_init():

// LAB 3: Your code here.
// declare of exception handler
void divide_error_handler();
void debug_exception_handler();
void non_maskable_interrupt_handler();
void breakpoint_handler();
void overflow_handler();
void bounds_check_handler();
void invalid_opcode_handler();
void device_not_available_handler();
void double_fault_handler();
void invalid_tss_handler();
void segment_not_present_handler();
void stack_exception_handler();
void general_protection_fault_handler();
void pagefault_handler();
void floating_point_error_handler();
void alignment_check_handler();
void machine_check_handler();
void simd_floating_point_error_handler();

// set up trap gate descriptor
SETGATE(idt[T_DIVIDE], 1, GD_KT, divide_error_handler, 0);
SETGATE(idt[T_DEBUG], 1, GD_KT, debug_exception_handler, 0);
SETGATE(idt[T_NMI], 1, GD_KT, non_maskable_interrupt_handler, 0);
SETGATE(idt[T_BRKPT], 1, GD_KT, breakpoint_handler, 3);
SETGATE(idt[T_OFLOW], 1, GD_KT, overflow_handler, 0);
SETGATE(idt[T_BOUND], 1, GD_KT, bounds_check_handler, 0);
SETGATE(idt[T_ILLOP], 1, GD_KT, invalid_opcode_handler, 0);
SETGATE(idt[T_DEVICE], 1, GD_KT, device_not_available_handler, 0);
SETGATE(idt[T_DBLFLT], 1, GD_KT, double_fault_handler, 0);
SETGATE(idt[T_TSS], 1, GD_KT, invalid_tss_handler, 0);
SETGATE(idt[T_SEGNP], 1, GD_KT, segment_not_present_handler, 0);
SETGATE(idt[T_STACK], 1, GD_KT, stack_exception_handler, 0);
SETGATE(idt[T_GPFLT], 1, GD_KT, general_protection_fault_handler, 0);
SETGATE(idt[T_PGFLT], 1, GD_KT, pagefault_handler, 0);
SETGATE(idt[T_FPERR], 1, GD_KT, floating_point_error_handler, 0);
SETGATE(idt[T_ALIGN], 1, GD_KT, alignment_check_handler, 0);
SETGATE(idt[T_MCHK], 1, GD_KT, machine_check_handler, 0);
SETGATE(idt[T_SIMDERR], 1, GD_KT, simd_floating_point_error_handler, 0);

问题1:
若是使用同一个处理程序,将无法限制调用错误处理程序的代码的特权级,也无法得知中断向量的值。

问题2:
仅有内核代码允许执行页错误处理程序,尽管调用了int $14,仍然因为保护机制而生成了中断向量13。如果内核允许int $14唤醒页错误处理程序,那么恶意的程序可以因此而随意触发缺页错误,导致系统无法正常工作。

第二部分 Page Faults, Breakpoints Exceptions, and System Calls - 页错误,断点异常和系统调用

处理页错误

页错误的中断向量号为14,是非常重要的异常。当处理器接收一个页错误时,会将引发页错误的线性地址存储在处理器控制寄存器CR2中。

练习5的代码如下,仅供参考:

1
2
3
4
5
// In trap_dispatch():
if (tf->tf_trapno == T_PGFLT) {
// dispatch page fault exceptions
page_fault_handler(tf);
}

断点异常

断点异常的中断向量号为3,通常被调试器用作向程序代码中添加断点,原理是将程序中的某一条指令暂时改为1字节的int3的软中断指令。在JOS中,将大量使用这一异常来实现一个原始的伪系统调用,使得用户环境可以使用它来环境JOS内核监视器,可以把内核监视器看做一个原始的调试器。
用户模式的panic,就是通过显示panic消息后执行int3实现的。

练习6的代码如下,仅供参考:

1
2
3
4
if (tf->tf_trapno == T_BRKPT) {
// dispatch breakpoint exceptions
monitor(tf);
}

问题3:
若是用特权级0初始化断点异常的IDT,那么会触发通用保护错误,这是因为用户模式的代码无法执行特权级0(内核模式)的处理程序,需要用特权级3初始化断点异常的IDT,这样才能使得断点测试正确通过。

问题4:
这些措施都是为了保护内核和用户环境的相互独立,使得用户环境仅能在收到允许的情况下执行某些内核的代码,保证了恶意程序不会破坏内核,窃取数据。同时也能保证用户环境能从内核得到必要的功能支持。

系统调用

用户进程通过系统调用请求内核为它工作。当用户进程唤醒系统调用时,处理器进入内核模式,处理器和内核合作保存用户进程状态,内核执行合适的代码完成系统调用,并恢复至用户进程。系统调用的具体实现随平台不同而不同。

JOS内核使用int $0x30作为系统调用。需要建立相关的中断描述符,注意中断向量0x30不可能由硬件生成,毫无疑问应该允许用户执行对应的处理程序。

应用程序会将系统调用号和系统调用参数存入寄存器中。避免了内核访问用户环境栈或是指令流。系统调用号放在寄存器%eax中,最多五个参数分别被相应地放在寄存器%edx, %ecx, %ebx, %edi%esi中。内核将返回值放在寄存器%eax中。唤醒系统调用的汇编代码已经提供为lib/syscall.c中的syscall()

练习7中遇到的问题如下:

  • syscall作为软中断不会压入错误码
  • 调用syscall函数时应当使用保存的栈帧中的寄存器值而非实际的寄存器值,原因是在函数调用间某些寄存器的值会发生改变
  • 练习7需要参考lib/syscall.c中得知参数的位置关系

练习7的代码如下,仅供参考:

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
// In trapentry.S:
TRAPHANDLER_NOEC(syscall_handler, T_SYSCALL)

// In trap.c, trap_init():
void syscall_handler();

SETGATE(idt[T_SYSCALL], 1, GD_KT, syscall_handler, 3);

// In kern/syscall.c, syscall():
// LAB 3: Your code here.

// panic("syscall not implemented");

switch (syscallno) {
case SYS_cputs:
// call sys_cputs
sys_cputs((const char *)a1, (size_t)a2);
break;
case SYS_cgetc:
// cll sys_cgetc
return sys_cgetc();
break;
case SYS_getenvid:
// call sys_getenvid
return sys_getenvid();
break;
case SYS_env_destroy:
// call sys_env_destroy
return sys_env_destroy((envid_t)a1);
break;
default: return -E_INVAL;
}

// will not reach here
return -E_UNSPECIFIED;

用户模式启动

一个用户在lib/entry.S的顶部开始运行,经过某些设置后,代码调用lib/libmain.c。你应当修改libmain()以初始化指向当前环境的struct Env指针thisenv(注意到lib/entry.S已经定义了指向你在第一部分映射的UENVSenvs)。

libmain()然后调用umain,对于hello程序而言,位于user/hello.c中。在打印hello, world后,它尝试访问thisenv->env_id。这也是为什么hello程序会出现fault

练习8中遇到的问题如下:

  • 可以使用宏ENVXenvid得到envenvs中的偏移量,而无需遍历整个envs
  • Lab2中pgdir_walk未设置PTE_U导致访问时出现了页错误(仅有PTE项中设置PTE_U是不足的)。

练习8的答案如下,仅供参考:

1
2
3
4
// In libmain.c, libmain():
// LAB 3: Your code here.
// get env id use system call and use ENVX to get index
thisenv = envs + ENVX(sys_getenvid());

页错误和内存保护

内存保护是操作系统的重要特性,保证了一个程序的错误不会毁坏内核或是其他的程序。
操作系统通常和硬件一起实现内存保护。操作系统负责告知硬件哪些虚拟地址是有效的、哪些是无效的。当一个程序试图去访问一个无效的地址或是一个没有权限的地址时,处理器在引起错误的指令处停止程序,然后带着相应的信息陷入内核。若错误可修复,则内核修复该错误并继续执行程序;若错误不可恢复,则程序无法继续运行。
现在考虑系统调用,系统调用允许用户程序向内核传递指针,内核在处理系统调用时将指针解引用,会出现以下两种问题:

  1. 内核的缺页错误潜在地比用户程序的缺页更加严重。若内核在操作私有的数据结构时发生缺页,那么将是内核自己的漏洞,错误处理程序应当panic内核。然而当内核解引用用户程序传递的指针时,需要某种方式标记由解引用导致的缺页实际上代表的是用户程序的利益。
  2. 内核比用户程序具有更多的权限。在这种情况下,用户程序可能传递给内核一个指针,该指针指向的内存只能被内核读写而不能被用户程序读写。在这种情况下,内核不能对该指针解引用,这么做会暴露私有数据或是破坏内核完整性。

当内核处理用户程序传递的指针时必须非常小心。内核必须检查用户传入的指针。

练习9和练习10遇到的问题如下:

  • 需要获取段寄存器的最低两位以得到段特权级

练习9和练习10的答案如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
// In kern/trap.c, page_fault_handler():
// LAB 3: Your code here.
if ((tf->tf_cs & 3) == 0) {
// code that causes page fault in kernel mode
panic("page fault in kernel!");
}

// In kern/pmap.c, user_mem_check():
int user_mem_check(struct Env *env, const void *va, size_t len, int perm) {
// LAB 3: Your code here.
if ((uintptr_t)va >= ULIM) {
// condition 1 - below ULIM violated
user_mem_check_addr = (uintptr_t)va;
return -E_FAULT;
}

uintptr_t va_start = (uintptr_t)ROUNDDOWN(va, PGSIZE);
uintptr_t va_end = (uintptr_t)ROUNDUP(va + len, PGSIZE);

for (; va_start < va_end; va_start += PGSIZE) {
// note we set page directory entry with less restrict
// we will only test page table entry here
pte_t *pgtable_entry_ptr =
pgdir_walk(env->env_pgdir, (char *)va_start, false);
if ((*pgtable_entry_ptr & (perm | PTE_P)) != (perm | PTE_P)) {
// condition 2 - permission violated
if (va_start <= (uintptr_t)va) {
// va lie in the first page and not aligned, return va
user_mem_check_addr = (uintptr_t)va;
} else if (va_start >= (uintptr_t)va + len) {
// va lie in the last page and exceed va + len, return va + len
user_mem_check_addr = (uintptr_t)va + len;
} else {
// return corresponding page's initial address
user_mem_check_addr = va_start;
}

return -E_FAULT;
}
}

// pass user memory check
return 0;
}

// In kern/syscall.c, syscall():
case SYS_cputs:
// checks memory before use sys_cputs to dereference a1
user_mem_assert(curenv, (char *)a1, (size_t)a2, PTE_U);
// call sys_cputs
sys_cputs((const char *)a1, (size_t)a2);
break;

// In kern/kdebug.c, debuginfo_eip():
// Make sure this memory is valid.
// Return -1 if it is not. Hint: Call user_mem_check.
// LAB 3: Your code here.
if (user_mem_check(curenv, usd, sizeof(struct UserStabData), PTE_U) < 0) {
return -1;
}

// Make sure the STABS and string table memory is valid.
// LAB 3: Your code here.
if ((user_mem_check(curenv, stabs, stab_end - stabs, PTE_U) < 0) ||
(user_mem_check(curenv, stabstr, stabstr_end - stabstr, PTE_U) < 0)) {
return -1;
}

发生了页错误的原因还要观察memlayout.h,在USTACKTOP上方有一个位于0xeebfd000Empty Memory,该虚拟地址没有映射任何的物理页。而在mon_backtrace的最后,访问到了位于此处的虚拟地址,因而导致了一个不可处理的页错误。

实验小结

最终执行make grade,评分脚本的输出如下:

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
36
37
38
39
40
41
42
divzero:
$ make run-divzero-nox-gdb QEMUEXTRA+=-snapshot
OK (1.3s)
softint:
$ make run-softint-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
badsegment:
$ make run-badsegment-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
Part A score: 30/30
faultread:
$ make run-faultread-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
faultreadkernel:
$ make run-faultreadkernel-nox-gdb QEMUEXTRA+=-snapshot
OK (0.9s)
faultwrite:
$ make run-faultwrite-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
faultwritekernel:
$ make run-faultwritekernel-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
breakpoint:
$ make run-breakpoint-nox-gdb QEMUEXTRA+=-snapshot
OK (2.0s)
testbss:
$ make run-testbss-nox-gdb QEMUEXTRA+=-snapshot
OK (2.1s)
hello:
$ make run-hello-nox-gdb QEMUEXTRA+=-snapshot
OK (1.0s)
buggyhello:
$ make run-buggyhello-nox-gdb QEMUEXTRA+=-snapshot
OK (1.8s)
buggyhello2:
$ make run-buggyhello2-nox-gdb QEMUEXTRA+=-snapshot
OK (2.1s)
evilhello:
$ make run-evilhello-nox-gdb QEMUEXTRA+=-snapshot
OK (1.1s)
Part B score: 50/50
Score: 80/80

至此,实验三结束。

第三个实验的难度明显比实验一和实验二大。
用户环境的管理相对简单,而设置陷阱和中断的部分涉及大量的x86硬件知识,需要大量参考Intel手册,要求直接写汇编代码设置栈帧也颇有挑战。

评论和共享

寒假在家终于有时间继续处理上学期没有做完的Labs,虽然效率偏低但总不是完全没有进展。
Lab2 - Memory Management主要包括了操作系统的内存管理,具体来说可以分为两部分。第一部分需要编写内核的物理内存分配器(Physical memory allocator),这会允许内核分配和释放内存。第二部分需要修改JOS的代码去实现一个虚拟内存,将虚拟地址映射到物理内存中。
2018年2月23日,完成了实验并写完了报告。

实验准备

根据实验官网的提示,依次切换到分支lab2并且合并分支lab1,在合并的过程中,没有发生冲突。

1
2
user% git checkout -b lab2 origin/lab2
user% git merge lab1

实验二包括如下的新文件:

  • inc/memlayout.h 描述了虚拟地址空间的结构
  • kern/pmap.c 需要修改、添加代码以完成实验
  • kern/pmap.h 定义了PageInfo结构 用来管理物理页状态
  • kern/kclock.h
  • kern/kclock.c 操作电池供电的时钟以及CMOS RAM硬件

实验过程

第一部分 Physical Page Management - 物理页管理

操作系统必须追踪物理内存以得知哪些内存是空闲的,以及哪些内存是正在被使用的。JOS使用页粒度管理PC的物理内存以便利用MMU映射和保护每一片被分配的内存。

实验的第一部分需要完成一个物理页面分配器,该分配器维护了一个struct PageInfo的链表来追踪空闲的物理页面(也就是空闲链表),空闲链表已经在CSAPP中有所了解,这里不再赘述。

具体来说,需要完成kern/pmap.c中实现以下的函数:

  • boot_alloc()
  • mem_init() (完成直到check_page_free_list(1)为止)
  • page_init()
  • page_alloc()
  • page_free()

完成后可以启动JOS去观察check_page_free_list()以及check_page_alloc()函数是否成功以检查编写的分配器的正确性。

第一部分的物理页面分配器总体来说难度不大,因为编写的分配器不像CSAPP中的malloc()一样,需要处理空闲内存的合并以及拆分,分配器只需要以物理页面为固定的粒度管理所有的内存即可。

在实际的Linux系统中,内核使用Buddy System快速地管理内存。

练习1的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// In boot_alloc():
// Allocate a chunk large enough to hold 'n' bytes, then update
// nextfree. Make sure nextfree is kept aligned
// to a multiple of PGSIZE.
//
// LAB 2: Your code here.
if (n == 0) {
// return the address of next free page
return nextfree;
} else if (n > 0) {
// round up size to a multiple of PGSIZE
size_t size = ROUNDUP(n, PGSIZE);
char * addr = nextfree;
// update address of next free page(still multiple of PGSIZE)
nextfree += size;
// nextfree is a kernel virtual address, out out memory when it exceeds 4 MB
if (nextfree >= (char *)KADDR(0x400000)) {
panic("out of memory when booting!");
}
// return address
return addr;
}

// In mem_init():
//////////////////////////////////////////////////////////////////////
// Allocate an array of npages 'struct PageInfo's and store it in 'pages'.
// The kernel uses this array to keep track of physical pages: for
// each physical page, there is a corresponding struct PageInfo in this
// array. 'npages' is the number of physical pages in memory. Use memset
// to initialize all fields of each struct PageInfo to 0.
// Your code goes here:
// get size of pages
uint32_t pages_size = sizeof(struct PageInfo) * npages;
// use boot_alloc to allocate memory
pages = (struct PageInfo *) boot_alloc(pages_size);
// initialization
memset(pages, 0, pages_size);

// In page_init():
size_t i;

// initialize from page 1 to page npages_basemem - 1
// set pp_ref to 0, set pp_link to last page_free_list
// and then update page_free_list
for(i = 1 ; i < npages_basemem ; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}

// calculate next free page and initialize corresponding pages entry
// convert from kernel virtual address to physical address
size_t next_free_page = PADDR(boot_alloc(0)) / PGSIZE;
pages[next_free_page].pp_link = &pages[npages_basemem - 1];
page_free_list = &pages[next_free_page];

// initialize remaining pages entry
for (i = next_free_page + 1 ; i < npages ; i++) {
pages[i].pp_ref = 0;
pages[i].pp_link = page_free_list;
page_free_list = &pages[i];
}

// In page_alloc():
struct PageInfo *
page_alloc(int alloc_flags)
{
// get first element in free list
struct PageInfo * page_ptr = page_free_list;
if (page_ptr != NULL) {
// NOT out of memory
// update free list
page_free_list = page_free_list->pp_link;
// get kernal virtual address from given page
char * addr = page2kva(page_ptr);
// set pp_link to NULL to allow double-free bugs check
page_ptr->pp_link = NULL;
// ALLOC_ZERO set, use memset to initialze physical page
if (alloc_flags & ALLOC_ZERO) {
memset(addr, 0, PGSIZE);
}

// return page
return page_ptr;
}

return NULL;
}

// In page_free():
void
page_free(struct PageInfo *pp)
{
// Fill this function in
// Hint: You may want to panic if pp->pp_ref is nonzero or
// pp->pp_link is not NULL.

//check pp_ref and pp_link
if (pp->pp_ref != 0) {
panic("page's reference count is non-zero!");
}
if (pp->pp_link != NULL) {
panic("double free error when free page!");
}

// return page to free list
pp->pp_link = page_free_list;
page_free_list = pp;
}

然后启动JOS,在终端观察到如下输出:

1
2
3
Physical memory: 131072K available, base = 640K, extended = 130432K
check_page_free_list() succeeded!
check_page_alloc() succeeded!

证明内存分配器工作正常。

第二部分 Virtual Memory - 虚拟内存

练习2:阅读Intel 80386 Reference Manual的第五章和第六章。主要阅读页翻译和页保护机制的部分。同时,也要对x86的分段机制有所了解。

虚拟地址、线性地址和物理地址

在x86中,虚拟地址由段选择子和段内偏移组成,通过段翻译机制,得到线性地址。线性地址经过页翻译机制,得到物理地址。物理地址就是实际的内存位置。

在实验1中,已经将线性地址0-4M映射到了虚拟地址0-4MKERNBASE-KERNBASE+4M。在本实验中,要将物理内存的低256M映射到从KERNBASE开始的虚拟地址。此外,还要映射其他几个虚拟地址空间。(KERNBASE0xf0000000

练习3:在QEMU监视器中使用xp命令检查物理内存0x00100000处的字,在gdb中使用x命令检查虚拟内存0xf0100000处的字,观察结果:

1
2
3
4
(qemu) xp 0x00100000
0000000000100000: 0x1badb002
(gdb) x/x 0xf0100000
0xf0100000 <_start+4026531828>: 0x1badb002

可以得出,物理地址0x00100000和虚拟地址0xf0100000上具有相同的数据。

info pginfo mem的输出如下:

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
(qemu) info pg
VPN range Entry Flags Physical page
[00000-003ff] PDE[000] ----A----P
[00000-00000] PTE[000] --------WP 00000
[00001-0009f] PTE[001-09f] ---DA---WP 00001-0009f
[000a0-000b7] PTE[0a0-0b7] --------WP 000a0-000b7
[000b8-000b8] PTE[0b8] ---DA---WP 000b8
[000b9-000ff] PTE[0b9-0ff] --------WP 000b9-000ff
[00100-00103] PTE[100-103] ----A---WP 00100-00103
[00104-00119] PTE[104-119] --------WP 00104-00119
[0011a-0011a] PTE[11a] ---DA---WP 0011a
[0011b-0011c] PTE[11b-11c] --------WP 0011b-0011c
[0011d-003ff] PTE[11d-3ff] ---DA---WP 0011d-003ff
[f0000-f03ff] PDE[3c0] ----A---WP
[f0000-f0000] PTE[000] --------WP 00000
[f0001-f009f] PTE[001-09f] ---DA---WP 00001-0009f
[f00a0-f00b7] PTE[0a0-0b7] --------WP 000a0-000b7
[f00b8-f00b8] PTE[0b8] ---DA---WP 000b8
[f00b9-f00ff] PTE[0b9-0ff] --------WP 000b9-000ff
[f0100-f0103] PTE[100-103] ----A---WP 00100-00103
[f0104-f0119] PTE[104-119] --------WP 00104-00119
[f011a-f011a] PTE[11a] ---DA---WP 0011a
[f011b-f011c] PTE[11b-11c] --------WP 0011b-0011c
[f011d-f03ff] PTE[11d-3ff] ---DA---WP 0011d-003ff

(qemu) info mem
0000000000000000-0000000000400000 0000000000400000 -r-
00000000f0000000-00000000f0400000 0000000000400000 -rw

在JOS内核中,uintptr_t代表虚拟地址,physaddr_t代表物理地址,它们都只是uint32_t的别名。因此,不能直接对其(int类型)解引用,需要先将其转换成指针类型。
对物理地址的解引用是错误的,因为MMU会将其当做虚拟地址,你将无法得到正确的内存内容。

问题1:
x的类型应当为uintptr_t,因为对其进行了解引用操作,所以x应当为虚拟地址。

有些时候,内核必须要处理物理地址,这也是要把0-4M映射到KERNBASE-KERNBASE+4M的理由。
为了能使内核读写物理地址,必须要加上KERNBASE,可以通过宏KADDR(pa)实现。
同理,有时候需要能通过虚拟地址找到物理地址,需要减去KERNBASE,可以通过宏PADDR(va)实现。

引用计数

在未来的实验中很可能将同样的物理页映射到多个虚拟地址,你需要在struct PageInfopp_ref域中保持物理页被引用的次数,当引用计数归0,页面不再被使用,可以被释放。
总的来说,引用计数应当等于物理页面在UTOP之下出现的次数(UTOP之上的物理页面大多在启动时被内核分配并且永远不应当被释放,所以不需要对其进行引用计数)。
引用计数也会被用来追踪指向页目录页的指针数,以及页目录对页表页的引用数。

在使用page_alloc()时应当小心,返回页的pp_ref应当很快被递增,如被别的函数如(page_insert())递增,在某些情况下,调用page_insert()的函数必须手动增加引用计数。

页表管理

需要编写管理页表的例程:插入和删除线性地址到物理地址的映射,当需要时创建页表等。

在练习4中遇到的问题总结如下:

  • pgdir_walk在设置页表项时应当使用物理地址,在返回指针时应当返回虚拟地址。这是因为此时实际的二级页表还未被设置应用,且0-4M被映射为只读,而KERNBASE-KERNBASE+4M被映射为可读可写。需要使用给出的宏而不要自己加减
  • 将PTE_P笔误成PTE_G
  • 在page_insert中提前将引用计数pp_ref自增就可以避免边界情况的错误
  • pgdir_walk中对于页目录的设置可以更宽松,否则可能会对之后的实验产生影响

练习4的代码如下,仅供参考:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
// In pgdir_walk():
pte_t *pgdir_walk(pde_t *pgdir, const void *va, int create) {
// get page directory index and page directory entry
size_t pgdir_index = PDX(va);
pde_t pgdir_entry = pgdir[pgdir_index];
// get page table index
size_t pgtable_index = PTX(va);
if ((pgdir_entry & PTE_P) == 1) {
// page table page exists
// get address of page table
pte_t *pgtable = KADDR(PTE_ADDR(pgdir_entry));
return (pte_t *)(pgtable + pgtable_index);
} else {
// page table page doesn't exist
if (create == false) {
// create flag is false, returns NULL
return NULL;
} else {
// allocate a new page table page
struct PageInfo *page = page_alloc(ALLOC_ZERO);
if (page == NULL) {
// allocation fails
return NULL;
} else {
// increase physical page's reference count
page->pp_ref++;
// get physical address of physical page
physaddr_t page_pa = page2pa(page);
// insert page table into page directory
pgdir[pgdir_index] = page_pa | PTE_W | PTE_U | PTE_P;
// NB: returns KERNEL VIRTUAL ADDRESS here, for 0-4M is NOT
// writable
return (pte_t *)page2kva(page) + pgtable_index;
}
}
}
return NULL;
}

// In boot_map_region():
static void boot_map_region(pde_t *pgdir, uintptr_t va, size_t size,
physaddr_t pa, int perm) {
// round up size
size = ROUNDUP(size, PGSIZE);
// get the number of pages to be mapped
size_t page_num = PGNUM(size);

size_t i;
for (i = 0; i < page_num; i++) {
// iterate through to get each pte_t * through pgdir_walk given virtual
// address
pte_t *pgtable_entry_ptr =
pgdir_walk(pgdir, (char *)(va + i * PGSIZE), true);
// set pte_t according to physical address and permission flags
*pgtable_entry_ptr = (pa + i * PGSIZE) | perm | PTE_P;
}
}

// In page_lookup():
struct PageInfo *page_lookup(pde_t *pgdir, void *va, pte_t **pte_store) {
// Fill this function in
pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, false);
if (pgtable_entry_ptr && ((*pgtable_entry_ptr) & PTE_P) == 1) {
if (pte_store != NULL) {
// pte_store not zero, store the address of pte of the page in it
*pte_store = pgtable_entry_ptr;
}
// converts from pa to page and returns
physaddr_t pa = PTE_ADDR(*pgtable_entry_ptr);
return pa2page(pa);
} else {
// no page mapped at va
return NULL;
}
return NULL;
}

// In page_remove():
void page_remove(pde_t *pgdir, void *va) {
// Fill this function in
pte_t *pgtable_entry_ptr = NULL;
// use page_lookup to get struct PageInfo
struct PageInfo *page = page_lookup(pgdir, va, &pgtable_entry_ptr);
if (page && pgtable_entry_ptr) {
// if page mapped at va
// decrease and try to free page
page_decref(page);
// set page table entry to 0
*pgtable_entry_ptr = 0;
// invalidate tlb
tlb_invalidate(pgdir, va);
}
}

// In page_insert():
int page_insert(pde_t *pgdir, struct PageInfo *pp, void *va, int perm) {
// Fill this function in
// try to get pointer to page table entry, created if needed
pte_t *pgtable_entry_ptr = pgdir_walk(pgdir, va, true);
if (!pgtable_entry_ptr) {
// page table cannot be allocated
return -E_NO_MEM;
}

// increase reference ahead of insertion to process CORNER CASE
pp->pp_ref++;

if (((*pgtable_entry_ptr) & PTE_P) != 0) {
// exists page mapped at va
// remove page and invalidate tlb
page_remove(pgdir, va);
}

// get physical address of page
physaddr_t pa = page2pa(pp);
// insert page into page table
*pgtable_entry_ptr = pa | perm | PTE_P;

// update permission flags of corresponding page directory
pgdir[PDX(va)] = pgdir[PDX(va)] | perm;

return 0;
}

第三部分 Kernel Address Space - 内核地址空间

JOS将32位的地址空间划为了两部分——用户环境(在Lab3中加载和运行)将控制低地址空间、而内核总是完全地控制高地址空间,由ULIM显式地划分地址空间。内核将占据约256M的地址空间。

尽管内核和用户内存位于同一地址空间,仍需要在x86的页表中使用权限位去保证用户代码仅能访问低地址空间。否则用户代码可能会覆写内核数据,导致故障。此外,用户代码还可能能从窃取其他用户、内核的私有数据。
在JOS中,用户环境将不具有ULIM以上任何内存的权限;只有内核可以读写这些内存。对于[UTOP, ULIM),内核和用户都仅能读而不能写,该段内存主要用于向用户暴露某些内核的只读数据结构;最后,UTOP以下的地址空间由用户环境使用,由用户环境自行设置这些内存的权限。

练习5的代码如下,仅供参考:

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
//////////////////////////////////////////////////////////////////////
// Now we set up virtual memory

//////////////////////////////////////////////////////////////////////
// Map 'pages' read-only by the user at linear address UPAGES
// Permissions:
// - the new image at UPAGES -- kernel R, user R
// (ie. perm = PTE_U | PTE_P)
// - pages itself -- kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, UPAGES, pages_size, PADDR(pages), PTE_U | PTE_P);

//////////////////////////////////////////////////////////////////////
// Use the physical memory that 'bootstack' refers to as the kernel
// stack. The kernel stack grows down from virtual address KSTACKTOP.
// We consider the entire range from [KSTACKTOP-PTSIZE, KSTACKTOP)
// to be the kernel stack, but break this into two pieces:
// * [KSTACKTOP-KSTKSIZE, KSTACKTOP) -- backed by physical memory
// * [KSTACKTOP-PTSIZE, KSTACKTOP-KSTKSIZE) -- not backed; so if
// the kernel overflows its stack, it will fault rather than
// overwrite memory. Known as a "guard page".
// Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KSTACKTOP - KSTKSIZE, KSTKSIZE, PADDR(bootstack),
PTE_W | PTE_P);

//////////////////////////////////////////////////////////////////////
// Map all of physical memory at KERNBASE.
// Ie. the VA range [KERNBASE, 2^32) should map to
// the PA range [0, 2^32 - KERNBASE)
// We might not have 2^32 - KERNBASE bytes of physical memory, but
// we just set up the mapping anyway.
// Permissions: kernel RW, user NONE
// Your code goes here:
boot_map_region(kern_pgdir, KERNBASE, 0xffffffff - KERNBASE, 0, PTE_W | PTE_P);

问题2:

Enrty Base Virtual Address Points to (logically)
1023 0xFFC00000 Physical Memory
……….
960 0xF0000000 First 4 MB on Physical Memory
959 0xEFC00000 Kernel Stack
957 0xEF400000 Kernel Page Directory
956 0xEF000000 Pages

问题3:
页保护机制实现了这一点,用户将不能访问未设置PTE_U的页(对于页目录和页表皆是如此)。

问题4:
注意到pages最多只有4MB,而一个struct PageInfo为8字节(对齐),所以实际上最多只有512K个项,总大小为2GB。

问题5:
使用了页表来管理虚拟内存,页表完整地映射了4GB的地址空间。使用pages追踪物理页面的情况,由于最初只映射了4MB,使得内存被限制在了2GB。

问题6:
执行转换的代码在entry.S中,和32位保护模式时相似:

1
2
mov	$relocated, %eax
jmp *%eax

实际的跳转是通过一次jmp实现的,得以继续执行的原因是引导时不仅将0-4M映射到了KERNBASE-KERNBASE+4M的读写,同时也映射到了0-4M的只读。不这么做的话将出现无法处理的SIGTRAP信号而导致系统Triple Fault。
不通过转换就无法在高地址执行内核代码,将内核映射在高地址主要是为了完整地映射内核的约256M空间。

实验小结

最终执行make grade,评分脚本的输出如下:

1
2
3
4
5
6
7
8
running JOS:
$ make qemu-nox-gdb
(1.3s)
Physical page allocator: OK
Page management: OK
Kernel page directory: OK
Page management 2: OK
Score: 70/70

至此,实验二结束。

第二个实验主要关注于操作系统的内存管理的基本概念,使用的也是简单的分配器,但是完整地描述了操作系统从引导直至内核初始化完毕是如何一步步设置页表,管理内存的。

由于已经在CSAPP(CMU 15213)中接触过相关的内存概念,本实验难度并不是很大。

评论和共享

前言

MIT6.828操作系统工程Lab1-Booting a PC实验报告中,出现了高版本gcc(> 7.1.1-3)编译出的JOS内核不能使用的问题(Triple Fault)。此外,gcc无法编译生成32位的JOS内核。因此需要手动降级到低版本并且开启gcc-multilib。

根据arch-dev-public,gcc-multilib已经被合并至了core/gcc之中。当然仍然可以通过Arch Linux Archive获取旧版本的gcc-multilib。

然而Arch是一个崇尚“Modernity”的发行版(参考Arch之道):

Arch尽全力保持软件处于最新的稳定版本,只要不出现系统软件包破损,都尽量用最新版本。

Arch Linux strives to maintain the latest stable release versions of its software as long as systemic package breakage can be reasonably avoided.

综合arch-dev-public对于gcc所做的改动和Arch之道,保持系统gcc为旧版本的gcc-multilib显然不是一个“优雅”的做法。最终,我决定按照6.828 Lab Tools的指导,手动编译gcc 4.6.1作为JOS内核的交叉编译工具链。

问题

编译gcc 4.6.1中遇到的问题以及解决方案总结如下:

  1. 网站上给出的部分软件包的下载链接已经过期。
  2. 网站上的教程默认将工具链安装在了/usr/local/下,这里为了管理上的方便没有采用默认的做法,而是将gcc直接安装在了home目录下(通过configure时的–prefix参数指定)。
  3. 接2,使用./comfigure –help获取帮助。在某些包configure时,需要使用如–with-mpc=… –with-gmp=…等参数来告知相应包的位置。
  4. 由于texinfo版本过高导致低版本的gcc不能正确编译,需要在configure时加上MAKEINFO=missing(当然,你也可以降级texinfo)。
  5. gcc 4.6.1的源码存在一个作用域错误问题。找到gcc/gengtype.c的write_field_root函数,将struct pair new;移动到函数的起始位置。
  6. 编译gcc时出现了libmpc.so.2库找不到的问题。需要修改环境变量LD_LIBRARY_PATH并添加相应的目录,或者也可以在configure的时候用参数–libdir指定库位置。
  7. gcc 4.6.1的源码存在一个数组访问越界错误,具体参考这里

Modules

包管理软件与环境变量

提一个简单的问题,当我们使用包管理软件(例如pacman)安装某个包(例如unzip)之后,在终端中输入unzip …即可解压zip文件。那么包管理软件究竟做了什么呢?

如果是从yaourt安装AUR的包,情况又会发生什么变化呢?

包管理软件主要管理各种包以及处理包与包之间的依赖问题。在安装包的时候,包管理软件从镜像源获取包,将包解压并且将内容复制到系统对应的位置。
诸如yaourt这样的包管理软件使用ABS(Arch Build System),根据pkgbuild文件的指导在本机下载源码、编译并打包,并且将生成的包安装到系统中。

以unzip-natspec为例(这是一个可以识别zip编码格式的unzip版本),我们使用pacman查看包的内容以及对应的位置:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
pacman -Ql unzip-natspec                       
unzip-natspec /usr/
unzip-natspec /usr/bin/
unzip-natspec /usr/bin/funzip
unzip-natspec /usr/bin/unzip
unzip-natspec /usr/bin/unzipsfx
unzip-natspec /usr/bin/zipgrep
unzip-natspec /usr/bin/zipinfo
unzip-natspec /usr/share/
unzip-natspec /usr/share/licenses/
unzip-natspec /usr/share/licenses/unzip/
unzip-natspec /usr/share/licenses/unzip/LICENSE
unzip-natspec /usr/share/man/
unzip-natspec /usr/share/man/man1/
unzip-natspec /usr/share/man/man1/funzip.1.gz
unzip-natspec /usr/share/man/man1/unzip.1.gz
unzip-natspec /usr/share/man/man1/unzipsfx.1.gz
unzip-natspec /usr/share/man/man1/zipgrep.1.g

可以看出unzip被放在/usr/bin目录下。可是为什么我们可以直接在终端中输入unzip …执行解压的命令而不是输入/usr/bin/unzip …呢?这就涉及到了环境变量PATH。

环境变量是一个动态命名的值,用来影响计算机上进程运行的行为。PATH设置了一组包含可执行文件的目录。在输入unzip的时候,终端默认会在PATH所包含的目录中寻找unzip,如果找到了就执行它。我们使用echo命令打印当前终端的环境变量。

1
2
echo $PATH
/home/user/intel/vtune_amplifier_2018.1.0.535340/bin64 /bin /usr/bin /usr/local/bin /usr/local/sbin /usr/lib/jvm/default/bin /usr/bin/site_perl /usr/bin/vendor_perl /usr/bin/core_perl /usr/lib/smlnj/bin /usr/bin/site_perl /usr/bin/vendor_perl /usr/bin/core_perl

6.828网站上默认将工具链安装在了/usr/local目录下,而/usr/local/bin是位于环境变量PATH中的。
因此,我们的qemu以及make可以直接找到编译好的工具链并调用。
现在,我们将工具链安装在了一个不属于PATH的目录中。对于这种情况,我们必须使用某种方式(如shell脚本),将相应目录添加PATH中。

对于我们编译的工具链,还需要设置环境变量LD_LIBRARY_PATH才可正常工作。LD_LIBRARY_PATH涉及linux的动态链接库(共享库),可以自行去搜索相关知识。

当我们安装的程序变多,脚本也会越变越多,管理诸如PATH的环境变量也变得不方便。
我们的jos内核使用的工具链加上了“i386-jos-elf”的前缀。若没有该前缀,添加环境变量后,终端会优先使用gcc 4.6.1作为默认的gcc,这显然不是我们期望的结果。
因此,我们可能还需要写另一个脚本,将相应的目录从PATH中移除。

此外,根据脚本的是否在终端启动时被执行,还可能出现不同终端环境不同的问题。

那么,有没有一种方法可以快速方便的管理不同软件以及他们所需要的环境变量呢?Modules正是一个可行的方法。

简介

Modules(Environment Modules)通过modulefile动态地改变用户环境。可以在Arch中安装env-modules(AUR)以使用Modules。

安装完毕后,需要编辑终端的配置文件来启用Modules。Modules的shell初始化放在/etc/modules/init文件夹下。

Modules使用Tcl作为脚本语言,编写modulefile时可以直接man modulefile获取帮助。

实例

给出管理jos工具链的modulefile,文件放置在/etc/modules/modulefiles文件夹下。使用module load jos加载环境,module unload jos取消环境。modulefile中的prepend-path扩展了环境变量PATH以及LD_LIBRARY_PATH。在调用unload的时候prepeng-path会自动被替换成remove-path。

jos

1
2
3
4
5
6
7
8
9
10
11
#%Module1.0
##
## modulefile
##
proc ModulesHelp {} {
puts stderr "Adds cross compile toolchain(gcc 4.6.1 i386) for MIT jos to user environment"
}
module-whatis "adds cross compile toolchain(gcc 4.6.1 i386) for MIT jos to user environment"
set root_dir /home/chenzhihao/6.828/gcc
prepend-path PATH $root_dir/bin
prepend-path LD_LIBRARY_PATH $root_dir/lib

评论和共享

最近开始阅读Structure of Interpretation of Computer Science即计算机程序的构造与解释这本书。该书中使用的是Scheme作为Lisp的方言。
在此之前华盛顿大学的《程序设计语言》这门课的PartB中,我使用的Lisp方言是Racket,配合DrRacket作为IDE使用。因为最近一直在配置vim,这一次打算使用vim作为主力开发环境。

如果你对我的配置文件(vim,tmux等)感兴趣,可以看这里

效果

最终的效果如下图所示:

思路

最初的思路来自于网上的一篇文章,作者也是正在阅读SICP这本书,其提到了使用tmux进行分屏,在一边使用vim进行代码的编辑,另一边运行mit-scheme作为REPL(Read-Eval-Print-Loop)解释scheme代码。

但是如果这么做的话,需要反复执行mit-scheme < source.scm,这样做显然不能提高我们编程的效率。

这几天逛友链博客的时候发现刚好Kyler也在读SICP并且配置了vim环境,具体可以参考这篇博客
受到这篇博客的启发,我决定使用vim-slime来“沟通”vim和tmux,将vim中的Scheme代码发送到运行在tmux中的解释器,并且运行给出结果。

在学习tmux的过程中我接触到了tmuxinator这个tmux配置管理工具。可以通过tmuxinator直接配置tmux session,十分方便。

要求

这篇博客的配置依赖于:

  1. vim(文本编辑器)
  2. tmux和tmuxinator(终端会话工具)
  3. mit-scheme(Scheme解释器)

实现

首先在家目录下的.tmuxinator子文件夹下创建新的配置文件scheme.yml:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# tmuxinator configuration file for scheme
# location: ~/.tmuxinator/scheme.yml

name: scheme
root: .

startup_window: main
socket_name: tmux_scheme

windows:
- main:
layout: even-horizontal
panes:
- vim <%= @args[0] %>
- mit-scheme

该配置文件指定新的scheme session拥有一个窗口main,该窗口有两个窗格,一个执行vim,另一个执行mit-scheme,并且创建的session的socket name为tmux_scheme。

然后我们在.vimrc中安装并配置vim-slime插件。
这里我直接使用插件管理器Vundle安装vim-slime:

1
Bundle 'jpalardy/vim-slime'

然后在.vimrc中加入配置:

1
2
3
4
5
6
7
8
9
" vim-slime configuration
" 设置目标为tmux
let g:slime_target = "tmux"
" 为tmux设置默认配置,指定socket_name为tmux_scheme,目标窗格为当前窗口的第2个窗格
let g:slime_default_config = {"socket_name": "tmux_scheme", "target_pane":":.1"}
" 指定slime在第一次发送代码时不要询问配置
let g:slime_dont_ask_default = 1
" 指定作为缓冲区的文件(该文件默认在执行完后不会被清空或者删除)
let g:slime_paste_file = "$HOME/.slime_paste"

vim-slime的默认快捷键是 (两次Ctrl-C)发送代码; v(Ctrl-C + v)修改配置。

最后编写测试文件test.scm,执行tmuxinator start scheme test.scm,在vim中按下两次Ctrl-C。应该能实现和上文效果图一样的效果。

其他

本篇博客只是给出了大概的环境配置的思路以及一些具体的配置文件。
如果想要深度地定制属于自己的Scheme开发环境,你可能还需要阅读vim、vim-slime、tmux、tmuxinator的文档与网上的教程。
配置的方式也不仅仅局限于tmux,gnu-screen、vim-terminal等同样能作为vim-slime连接的目标。
配置的环境也不必仅仅局限于Scheme,python、sml等解释型语言均可使用。

评论和共享

本学期开设了操作系统的专业课。根据老师的介绍,下个学期的操作系统课设就是MIT的6.828的Labs,再加上团队老学长/同学的推荐,打算先在这个学期完成6.828,加深对于系统的理解。
Lab1 - Booting a PC是比较简单的实验,主要包括了引导、内核、控制台输出、以及栈。尽管如此,由于相关知识的缺失,我断断续续做了2周(2017年10月26日)才完成该实验。
2017年12月9日,完成了实验的提高部分并写完了报告。

实验准备

首先需要完成实验环境的搭建。实验环境主要由两个部分组成:QEMU用来模拟运行内核,以及一条编译工具链用于编译和测试内核。这里我使用的系统是64位的ArchLinux。

本部分可以参考MIT 6.828官网的Tools

编译工具链

编译工具链包含了C编译器、汇编器、连接器,用于从源代码生成可执行二进制文件。本实验的目标代码是32位的Intel架构(x86),可执行文件格式为ELF。

在Arch Linux下,若是在安装时选择了base-devel包组,则gcc应该是系统自带的编译工具链。但是,该gcc默认不能编译生成32位的可执行文件。需要手动开启multilib并安装gcc-multilib以及相关的软件包。

GCC版本降级说明

在我和华田的Arch下,使用gcc 7.1.1-3之后的版本编译生成的JOS kernel均无法使用。在无法查明原因的情况下,推荐将gcc降级至7.1.1-3完成6.828的实验。

有关于Arch下软件包降级的教程请看这里

在后续的实验中,为了使得编译JOS内核的工具链不和系统工具链冲突以及为了保证系统工具链的最新,尝试了手动编译32位的gcc 4.6.1作为JOS专用的交叉编译工具链,并使用modules来管理环境变量,具体可以参考这里

Qemu模拟器

QEMU是一个现代并且快速的PC模拟器,但是为了与实验兼容,MIT推荐使用他们patched过的QEMU版本。需要按照Tools上的教程从源码编译并安装QEMU。

注意:提供的QEMU并不支持make uninstall,需要手动卸载QEMU。如果您对于手动编译并安装可能存在的后果抱有顾虑,推荐使用包管理软件安装QEMU,或是修改编译前缀,不要将编译好的qemu安装到/usr/local/

问题

  1. 所需要的库名可以在arch官网上通过搜索软件包的方式找到;
  2. configure的时候加上–disable-werror以保证不会因出现编译警告而终止编译;
  3. 出现如下错误:

    1
    2
    3
    4
    5
    Unescaped left brace in regex is illegal here in regex; marked by <-- HERE
    in m/^\@strong{ <-- HERE (.*)}$/ at /home/guest/qemu/scripts/texi2pod.pl
    line 320.

    make: *** [Makefile:474:qemu.1] 错误 255。

    该错误是由于perl版本更新后正则表达式语法的变动造成的,直接修改安装脚本的/home/chenzhihao/qemu/scripts/texi2pod.pl line 320,将{改成 \{即可;

  4. configure时可能需要指定python版本为2以避免调用python3出现错误,参数为--python=/usr/bin/python2.7

实验介绍

实验1总共分为3个部分:

  • 第1部分主要关注x86汇编语言、QEMU x86模拟器以及PC的上电启动流程;
  • 第2部分主要关注6.828内核的引导程序;
  • 第3部分开始挖掘6.828内核的最初模板 - JOS。

实验使用Git进行版本管理,需要从MIT的Git克隆最开始的仓库,有关这一部分的具体说明请自行参考Lab1实验讲义

有关于Git的教程推荐廖雪峰的官方博客或者是Pro Git 2

实验过程

第一部分 PC Bootstrap - PC引导

x86汇编

练习1:
本实验需要熟悉x86汇编。

8086汇编已经在王爽的《汇编语言》以及学院的汇编语言课程中学习过,x86_64汇编也已经在《深入理解计算机系统》中有所涉猎。本实验中使用的是i386汇编。这里不再赘述。

模拟x86

在本实验中使用QEMU作为模拟器。尽管QEMU内置的监控只能提供少量的调试支持,但是QEMU却可以作为GNU-Debugging(GDB)的远程调试目标。

根据实验指导使用make编译生成内核并且用make qemu或者是make qemu-nox启动QEMU。可以看到,当前的内核仅支持两条命令help和kerninfo。

PC的物理地址空间

PC的物理地址空间有着如下的布局:

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
+------------------+  <- 0xFFFFFFFF (4GB)
| 32-bit |
| memory mapped |
| devices |
| |
/\/\/\/\/\/\/\/\/\/\

/\/\/\/\/\/\/\/\/\/\
| |
| Unused |
| |
+------------------+ <- depends on amount of RAM
| |
| |
| Extended Memory |
| |
| |
+------------------+ <- 0x00100000 (1MB)
| BIOS ROM |
+------------------+ <- 0x000F0000 (960KB)
| 16-bit devices, |
| expansion ROMs |
+------------------+ <- 0x000C0000 (768KB)
| VGA Display |
+------------------+ <- 0x000A0000 (640KB)
| |
| Low Memory |
| |
+------------------+ <- 0x00000000

最初的PC基于Intel的16位8088处理器,仅能够支持2^20B = 2^10KB = 1MB的寻址,早期的地址空间从0x00000开始到0xFFFFF结束。

  • 0x00000到0xA0000(640KB)被称作低内存,是早期PC能用的唯一的RAM;
  • 0xA0000到0xFFFFF(384KB)被硬件保留作特殊用途如视频缓冲区或是固件,该部分最重要的区域是从0xF0000到0xFFFFF(64KB)的基本输入输出系统(BIOS)。BIOS用作执行最基本的系统初始化如激活显卡、检查内存等。在初始化完成后,BIOS从软盘、硬盘、光驱或是网络中读取操作系统,并且将机器控制权转移给操作系统。

从Intel的80286到80386,处理器能够支持16MB和4GB的地址空间。但为了后向兼容性,硬件设计者保留了低1M内存的布局。
现代PC因此在0x000A0000到0x00100000的内存中有一个“洞”,这个洞将内存分为了低内存/保留内存(Low Memory)(低640KB)以及扩展内存(Extended Memory)(其他内存)。除此以外,32位PC的地址空间的最上方,常常被BIOS保留用作32位的PCI设备。

最新的x86处理器能够支持超过4GB的物理内存,因此内存可以超过0xFFFFFFFF。因此BIOS需要预留出第二个“洞”以保证那些32位的PCI设备的地址可以被正确的映射。

由于JOS只会使用256M内存,在此假设仅PC具有32位的地址空间。

ROM BIOS

根据实验指导,进行QEMU和GDB的联合调试。会发现从上电开始,IBM PC从0x000ffff0开始执行指令。该处位于为BIOS预留的64kb的空间的顶层。此时CS = 0xf000 IP = 0xfff0。且第1条指令是一个jmp指令,跳转至CS = 0xf000 IP = 0xe05b。

这些都是早期的8088处理器的设计者设计的。这样的设计保证了BIOS总能控制机器。因为在刚上电的时候,在内存中并不存在能够执行的代码。

此处需要理解8086的分段式寻址,即通过两个16位寄存器的值构造20位地址。实际地址为CS × 16 + IP = 0xf000 × 16 + 0xfff0 = 0xffff0。

练习2:
使用gdb的si(单步调试)命令进入ROM BIOS并追踪几条指令,并猜测这些指令的作用。不需要指出指令具体的细节,只要理解BIOS一开始运行的核心思想而已。

BIOS执行的前若干条指令和作用如下:

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
[f000:fff0]    0xffff0: ljmp   $0xf000,$0xe05b # 跳到一个较早的位置
[f000:e05b] 0xfe05b: cmpl $0x0,%cs:0x6ac8
[f000:e062] 0xfe062: jne 0xfd2e1 # 测试cs段的0x6ac8字是否为0
[f000:e066] 0xfe066: xor %dx,%dx # 测试为0
[f000:e068] 0xfe068: mov %dx,%ss
[f000:e06a] 0xfe06a: mov $0x7000,%esp # 设置栈段寄存器和栈指针寄存器
# 栈的延伸方向和代码段延伸方向相反
[f000:e070] 0xfe070: mov $0xf34c2,%edx # 设置edx寄存器值
[f000:e076] 0xfe076: jmp 0xfd15c # 跳转
[f000:d15c] 0xfd15c: mov %eax,%ecx
[f000:d15f] 0xfd15f: cli # 关闭硬件中断
[f000:d160] 0xfd160: cld # 设置串传送指令方向
[f000:d161] 0xfd161: mov $0x8f,%eax
[f000:d167] 0xfd167: out %al,$0x70 # 关闭不可屏蔽中断
[f000:d169] 0xfd169: in $0x71,%al # 从CMOS读取选择的寄存器
[f000:d16b] 0xfd16b: in $0x92,%al # 读取系统控制端口A
[f000:d16d] 0xfd16d: or $0x2,%al
[f000:d16f] 0xfd16f: out %al,$0x92 # 通过快速A20以启动A20
[f000:d171] 0xfd171: lidtw %cs:0x6ab8 # 将cs:0x6ab8加载进入IDT表
[f000:d177] 0xfd177: lgdtw %cs:0x6a74 # 将cs:0x6a74加载进入GDT表
[f000:d17d] 0xfd17d: mov %cr0,%eax
[f000:d180] 0xfd180: or $0x1,%eax
[f000:d184] 0xfd184: mov %eax,%cr0 # 将cr0寄存器的保护模式位打开
[f000:d187] 0xfd187: ljmpl $0x8,$0xfd18f # 通过ljmp指令进入保护模式
=> 0xfd18f: mov $0x10,%eax # 设置段寄存器
=> 0xfd194: mov %eax,%ds
=> 0xfd196: mov %eax,%es
=> 0xfd198: mov %eax,%ss
=> 0xfd19a: mov %eax,%fs
=> 0xfd19c: mov %eax,%gs
=> 0xfd19e: mov %ecx,%eax
=> 0xfd1a0: jmp *%edx # 跳转

第二部分 引导

软盘和硬盘被分为了512Bytes的区域 - 扇区(Sector)。一个扇区是磁盘传输的最小粒度:每一个读操作和写操作必须是一个或是一个以上的扇区,并且必须要对齐到扇区。

如果一个磁盘是可引导的,那么它的第一个扇区就被称作引导扇区,引导代码就存储在引导扇区中。如果BIOS发现了一个可引导的硬件,那么它就将这个扇区从磁盘读取至内存的0x7c00到0x7dff处,并且使用一个jmp指令设置CS:IP = 0000:7C00,将控制传递给引导。和BIOS读取地址一样,这个地址对于PC来说是固定和标准化的。

从光盘引导的情形更加复杂,因为光盘的一个扇区为2048Byte,BIOS可以从硬盘读取一个更大的引导镜像到内存中。

在6.828中,使用硬盘的传统引导机制。这意味这引导必须满足512个Bytes的限制。引导由一个汇编文件boot/boot.S,以及一个C语言文件boot/main.c组成。

练习3:追踪boot.S和main.C,分析每一个部分的作用。


为了理解boot.S,需要以下的知识储备。

实模式和保护模式

实模式是为了与8086兼容而设置的。在实模式下,处理器相当于一个快速的8086处理器。当处理器被加电或者复位时以实模式启动。

  • 实模式下各寄存器以实模式的初始化值工作;
  • 实模式的地址空间总共为20位(1MB);
  • 实模式下不支持内存分页机制;
  • 实模式下各内存段均是可读、可写、可执行的,不支持指令优先级,所有的指令均运行在特权级;
  • 实模式不支持多任务切换;
  • 实模式的中断处理也和8086相同,使用中断向量表来定位中断服务程序。

在保护模式下,处理器的所有功能都是可用的。具体来说:

  • 保护模式提供了完全的32位地址空间,寻址空间为4GB;
  • 保护模式支持内存分页机制,提供了对虚拟内存的硬件支持;
  • 保护模式的处理器支持多任务(上下文切换);
  • 保护模式的处理器支持指令和数据的特权级,配合边界检查等机制,既可以共享数据也可以隔离各个任务。

为了保证后向兼容性,x86的处理器启动时默认是实模式,需要手动从实模式切换至保护模式。但是切换至保护模式之前需要做一些必要的准备工作,如打开A20和建立全局描述符表等。

A20地址线

在早期的PC上处理器仅支持20位的地址空间,任何超过20位的地址都会被卷回。
例如:0xFFFF+0xFFFF = 0x1FFFE -> 0xFFFE

然而,从80286开始,Intel支持了24位的地址空间,上例的地址相加将不会发生卷回。
为了保证与早期PC的完全兼容,Intel采用了“黑魔法” - 将A20(第21根)地址线与键盘控制器的一个输出进行了与运算。进而控制A20地址线的值。

默认情况下,A20是置0的,PC将只能访问1M、3M、5M…这样的奇数段。进入保护模式前需要先打开A20以获得完全的寻址能力。

JOS内核通过端口的方式与键盘控制器进行通信并打开A20。可以参考Reference中的PS/2 Keyboard Interface

  • 8042有一个1 Byte的输入缓冲区,一个1 Byte的输出缓冲区、一个1 Byte的状态寄存器、以及一个1 Byte的控制寄存器。前三个寄存器可以直接从0x60和0x64端口进行访问。最后一个寄存器通过“Read Command Byte”命令进行读,通过“Write Command Byte”命令进行写。
  • 对0x60端口读会读输入缓冲区;对0x60端口写会写输出缓冲区;对0x64端口读会读状态寄存器;对0x64端口写会发送命令。
  • 状态寄存器的Bit1为IBF - Input Buffer Full,当该Bit为1时,输入缓冲区满,不能对0x60端口或0x64端口写。
  • 对0x64端口写0xd1发送的命令是“Write Output Port”写输出端口,表明将参数写入输出端口(0x60端口写)。
  • A20使用的是键盘控制器输出的Bit 1,向输出端口写入0xdf可以打开A20;向输出端口写入0xdd则会关闭A20。

分段机制与全局描述符表

x86处理器提供了分段机制和分页机制两种内存管理模式。如果要进入保护模式,就必须要先启动分段机制。(分页机制不是必须的)

分段机制将内存划分为若干个段,每个段都由段基址、段界限和段属性组成。由一个段描述符表(可以理解为一个数组)描述所有段的信息。段描述符表可以是全局的也可以是局部的。

简化的说,程序首先将对应的段选择子(可以理解为数组的索引)加载进入段寄存器中。然后在执行程序时,根据指令的内容确定应该使用的段寄存器,根据段寄存器中的段选择子确定应该使用的段描述符。再结合段描述符中包含的信息加上指令自身的地址构造出实际的物理地址。最终将该地址发送到地址总线上,到物理内存中寻址,并取回相应的数据。这之中简化了有关特权级、边界检查的相关内容,但足以描述分段机制的基本原理。

分段机制将虚拟地址转换成了线性地址。

全局描述符表寄存器

x86处理器提供了专门的全局描述符表寄存器(Global Descriptor Table Register)用于保存全局描述符表的表基址和表限长。GDTR由2个字节的表限长(limit)和4个字节的表基址(base)组成。其中表基址指定了全局描述符表的起始地址,表限长指定了全局描述符表的大小。其C结构体描述如下:

1
2
3
4
struct gdtr {
u16 limite;
u32 base;
} __attribute__ ((packed));

在机器刚加电或者是处理器复位后,表基址默认被置为0,表限长则默认被置为0xFFFF。在保护模式初始化的过程中,必须给GDTR加载新的值。可以使用lgdt指令为GDTR加载新值。

段选择子

段选择子(2个字节)用于选择特定的描述符表以及表中的特定描述符。段选择子一般被放置于段寄存器中,段选择子由13位的索引、1位的表指示位和2位的请求特权级三部分组成。其中索引指定了描述符,表指示位选择应该访问的描述符表 - 0代表全局描述符表,1代表局部描述符表,请求特权级用于段级的保护机制,自0到4分别代表ring 0到ring 3。其C结构体描述如下:

1
2
3
4
5
struct selector {
u16 index:13;
u16 ti:1;
u16 rpl:2;
}

段描述符

段描述符(8个字节)是段描述符表这个“数组”的“元素”。用C结构体描述如下:

1
2
3
4
5
6
7
8
9
struct gdtdesc {
u16 lim0_15;
u16 base0_15;
u8 base16_23;
u8 acces;
u8 lim16_19:4;
u8 other:4;
u8 base24_31;
} __attribute__ ((packed));

其中总共包含了32位的段基址、20位的段界限、以及12位的类型。
段基址规定了段的起始地址。段界限规定了段的大小。而类型用于区别不同类型的描述符。包括描述符特权级、段存在位、已访问位等等。

boot.S代码详解

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <inc/mmu.h>

# Start the CPU: switch to 32-bit protected mode, jump into C.
# The BIOS loads this code from the first sector of the hard disk into
# memory at physical address 0x7c00 and starts executing in real mode
# with %cs=0 %ip=7c00.
# boot.S 主要将CPU切换至32位保护模式,并且跳转进入C代码

.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

.globl start
start: # 程序入口
.code16 # Assemble for 16-bit mode 指导生成16位汇编代码
cli # Disable interrupts 关中断
cld # String operations increment 设置串传递顺序递增

# Set up the important data segment registers (DS, ES, SS). 设置重要的段寄存器为0
xorw %ax,%ax # Segment number zero
movw %ax,%ds # -> Data Segment
movw %ax,%es # -> Extra Segment
movw %ax,%ss # -> Stack Segment

# Enable A20:
# For backwards compatibility with the earliest PCs, physical
# address line 20 is tied low, so that addresses higher than
# 1MB wrap around to zero by default. This code undoes this.
# 开启A20:
# A20的介绍已经给出,不再赘述。
seta20.1:
inb $0x64,%al # Wait for not busy 等待缓冲区可用
testb $0x2,%al # Test for bit1
# if bit1 = 1 then buffer is full
jnz seta20.1

movb $0xd1,%al # 0xd1 -> port 0x64
outb %al,$0x64 # Prepare to write output port 准备写入输出端口

seta20.2:
inb $0x64,%al # Wait for not busy 等待缓冲区可用
testb $0x2,%al
jnz seta20.2 # The same as above 同上

movb $0xdf,%al # 0xdf -> port 0x60
outb %al,$0x60 # 0xdf -> A20 gate enable command 打开A20

# Switch from real to protected mode, using a bootstrap GDT
# and segment translation that makes virtual addresses
# identical to their physical addresses, so that the
# effective memory map does not change during the switch.
lgdt gdtdesc # Load gdt size/base to gdtr 设置全局描述符表
movl %cr0, %eax # Control register 0
# bit0 is protected enable bit
# 读取控制寄存器0的值,其Bit0为允许保护模式位
orl $CR0_PE_ON, %eax # Set PE 将允许保护模式位置1
movl %eax, %cr0 # Update Control register 0 设置控制寄存器0

# Jump to next instruction, but in 32-bit code segment.
# Switches processor into 32-bit mode.
ljmp $PROT_MODE_CSEG, $protcseg # 通过ljmp指令(跳转至下一条指令)进入保护模式

.code32 # Assemble for 32-bit mode 指导生成32位汇编代码
protcseg:
# Set up the protected-mode data segment registers 设置保护模式的数据段寄存器
movw $PROT_MODE_DSEG, %ax # Our data segment selector
movw %ax, %ds # -> DS: Data Segment
movw %ax, %es # -> ES: Extra Segment
movw %ax, %fs # -> FS
movw %ax, %gs # -> GS
movw %ax, %ss # -> SS: Stack Segment

# Set up the stack pointer and call into C. 设置栈指针并且调用C
movl $start, %esp # Stack has the opposite extension direction than Code
# 注意栈的延伸方向和代码段相反
call bootmain #调用main.c中的bootmain函数

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

# Bootstrap GDT 引导GDT
.p2align 2 # force 4 byte alignment
gdt:
SEG_NULL # null seg 默认第一个段描述符为空
SEG(STA_X|STA_R, 0x0, 0xffffffff) # code seg 设置代码段描述符
SEG(STA_W, 0x0, 0xffffffff) # data seg 设置数据段描述符
# 关于SEG宏可以参考mmu.h

gdtdesc: # 用于设置全局段描述符寄存器
.word 0x17 # sizeof(gdt) - 1 # Size of gdt
.long gdt # address gdt # Base address of gdt

为了理解main.c,需要如下的知识储备。

ELF文件格式

可执行和可链接格式(Executable and Linkable Format)是一种用于二进制文件、可执行文件、目标代码、共享库和核心转储格式文件。

ELF文件可以分为两种组成 - 链接视图(Linking View)和执行视图(Execution View)。这里只讨论执行视图。

执行视图的结构如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
+--------------------+
| ELF Header |
+--------------------+
|Program Header Table|
+--------------------+
| Segment 1 |
+--------------------+
| Segment 2 |
+--------------------+
| ... |
+--------------------+
|Section Header Table|
| optinal |
+--------------------+

ELF文件格式主要由ELF头(ELF Header)、程序头部表(Program Header Table)和节头部表(Section Header Table)组成。在执行视图中,节头部表是可选的。

有关于这些数据结构的C语言定义可以参考头文件<inc/elf.h>。

  • ELF头主要包含了ELF魔数、文件类型、程序头部表偏移和大小、程序入口等信息;
  • 程序头部表可以看做一个数据结构的数组,每一个元素都描述了一个段。主要包含了段的偏移、段的虚拟地址、段的物理地址、段的大小等信息。

磁盘控制器

磁盘是电脑主要的存储媒介。磁盘是由盘片构成的。每个盘片有两面或者称为表面,表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴,它使得盘片以固定的旋转速率旋转,通常是5400-15000转每分钟(Revolution Per Minute)。磁盘通常包含一个或多个这样的盘片,并封装在一个密封的容器内。

每一个表面是由一组称为磁道的同心圆组成。每个磁道被划分为一组扇区。每个扇区包含相等数量的数据位(通常是512字节),这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙分隔开,这些间隙中不存储数据位。间隙用来标识扇区的格式化位。

磁盘的柱面是所有盘片表面上到主轴中心距离相等的磁道的集合。

对于磁盘的寻址通常分为CHS和LBA两种。

  1. CHS即柱面(cylinder)-磁头(head)-扇区(sector)寻址。每个盘片都对应着一个磁头,每一个盘片都被划分成柱面,每一个柱面都被划分成多个段。磁盘的最小存储单元是段。早期的IBM PC架构上采用CHS进行磁盘寻址。CHS是一个三元组,包括10bit的柱面号,8bit的磁头号以及6bit的扇区号。这样CHS的最大寻址范围为2^10 × 2^8 × 2^6 × 512 = 8GB。
  2. 随着磁盘容量的不断扩大,CHS的8GB寻址范围已经不能满足需要,现在的磁盘普遍采用逻辑区块地址(Logical Block Adress)的方式进行寻址来进行抽象。LBA是一个整数,代表磁盘上的一个逻辑区块编号,通过将这个整数转换成CHS格式来完成磁盘的具体寻址。LBA为48个bit,最大寻址范围为128PB。在本实验中,LBA按照旧的规范采用28个bit。

IDE硬盘控制器(IDE Hard Drive Controller)的0x1F7端口读为磁盘0状态寄存器。
其Bit6为RDY Bit,当其置1表明磁盘上电完成。在对于磁盘做任何操作(除了复位)之前务必要保证该Bit为1。
其Bit7为BSY Bit,当其置1表明磁盘忙。在你向磁盘发送任何指令前务必保证该Bit为0。

通过IDE硬盘控制器读取扇区需要如下的步骤:

  1. 向0x1F2端口写入待操作的扇区数目;
  2. 向0x1F3-0x1F5端口依次写入LBA的低24位;
  3. 向0x1F6端口的低4位写入LBA的高4位,向0x1F6端口的高4位写入驱动器地址;
  4. 向0x1F7端口写入读命令0x20。

0x1F6寄存器又称Drive/Head寄存器。其低4位是LBA的高4位。其Bit5和Bit7一般是1。其Bit6为LBA位,当置1时表示启用LBA寻址。其Bit4为DRV位。用来选择驱动器,Master驱动器为0,Slave驱动器为1。这里将高4位置为0x1110

在使用读命令0x20之前需要完整的设置柱面/磁头/扇区。当这个命令完成,你可以从磁盘的数据寄存器(0x1F0端口)读取256个字(16Bits)。

main.c代码详解

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <inc/elf.h>
#include <inc/x86.h>

/**********************************************************************
* This a dirt simple boot loader, whose sole job is to boot
* an ELF kernel image from the first IDE hard disk.
*
* DISK LAYOUT
* * This program(boot.S and main.c) is the bootloader. It should
* be stored in the first sector of the disk.
*
* * The 2nd sector onward holds the kernel image.
*
* * The kernel image must be in ELF format.
*
* BOOT UP STEPS
* * when the CPU boots it loads the BIOS into memory and executes it
*
* * the BIOS intializes devices, sets of the interrupt routines, and
* reads the first sector of the boot device(e.g., hard-drive)
* into memory and jumps to it.
*
* * Assuming this boot loader is stored in the first sector of the
* hard-drive, this code takes over...
*
* * control starts in boot.S -- which sets up protected mode,
* and a stack so C code then run, then calls bootmain()
*
* * bootmain() in this file takes over, reads in the kernel and jumps to it.
**********************************************************************/

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

void readsect(void *, uint32_t);
void readseg(uint32_t, uint32_t, uint32_t);

void bootmain(void) {
struct Proghdr *ph, *eph;

// read 1st page off disk 从磁盘上读取第一页
readseg((uint32_t)ELFHDR, SECTSIZE * 8, 0);

// is this a valid ELF? 通过ELF魔数确认ELF有效
if (ELFHDR->e_magic != ELF_MAGIC) goto bad;

// load each program segment (ignores ph flags) 读取各个段
ph = (struct Proghdr *)((uint8_t *)ELFHDR + ELFHDR->e_phoff);
// 程序头部表的起始地址
eph = ph + ELFHDR->e_phnum; // 程序头部表的结束地址
for (; ph < eph; ph++)
// p_pa is the load address of this segment (as well
// as the physical address)
// p_pa是加载地址也是物理地址
readseg(ph->p_pa, ph->p_memsz, ph->p_offset);

// call the entry point from the ELF header 从ELF头调用程序入口
// note: does not return!
((void (*)(void))(ELFHDR->e_entry))();

bad:
// stops simulation and breaks into the debug console
outw(0x8A00, 0x8A00);
outw(0x8A00, 0x8E00);
while (1) /* do nothing */;
}

// Read 'count' bytes at 'offset' from kernel into physical address 'pa'.
// 从内核的offset处读取count个字节到物理地址pa处
// Might copy more than asked 可能会读取超过count个(扇区对齐)
void readseg(uint32_t pa, uint32_t count, uint32_t offset) {
uint32_t end_pa;

end_pa = pa + count; // 结束物理地址

// round down to sector boundary 对齐到扇区
pa &= ~(SECTSIZE - 1);

// translate from bytes to sectors, and kernel starts at sector 1
offset =
(offset / SECTSIZE) + 1; // 算出扇区数 注意扇区从1开始(0为引导扇区)

// 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.
// 在实际中往往将多个扇区一起读出以提高效率。
while (pa < end_pa) {
// Since we haven't enabled paging yet and we're using
// an identity segment mapping (see boot.S), we can
// use physical addresses directly. This won't be the
// case once JOS enables the MMU.
// 考虑到没有开启分页以及boot.S中使用了一一对应的映射规则,
// 加载地址和物理地址是一致的。
readsect((uint8_t *)pa, offset);
pa += SECTSIZE;
offset++;
}
}

void waitdisk(void) {
// wait for disk reaady 等待磁盘准备完毕。
while ((inb(0x1F7) & 0xC0) != 0x40) /* do nothing */;
}

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

outb(0x1F2, 1); // count = 1 0x1F2 Disk 0 sector count
// Read one sector each time
outb(0x1F3, offset); // Disk 0 sector number (CHS Mode)
// First sector's number
outb(0x1F4, offset >> 8); // Cylinder low (CHS Mode)
outb(0x1F5, offset >> 16); // Cylinder high (CHS Mode)
// Cylinder number
outb(0x1F6, (offset >> 24) | 0xE0); // Disk 0 drive/head
// MASK 11100000
// Drive/Head Register: bit 7 and bit 5 should be set to 1
// Bit6: 1 LBA mode, 0 CHS mode
outb(0x1F7, 0x20); // cmd 0x20 - read sectors
/*20H Read sector with retry. NB: 21H = read sector
without retry. For this command you have to load
the complete circus of cylinder/head/sector
first. When the command completes (DRQ goes
active) you can read 256 words (16-bits) from the
disk's data register. */

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

// read a sector
insl(0x1F0, dst, SECTSIZE / 4);
// Data register: data exchange with 8/16 bits
// insl port addr cnt: read cnt dwords from the input port
// specified by port into the supplied output array addr.
// dword: 4 bytes = 16 bits
}

练习3:

  1. 0x7c2d: ljmp $0x8, $0x7c32 从这句汇编指令之后处理器开始执行32位指令。ljmp指令导致了16位指令到32位指令的转变。
  2. 引导最后执行的指令是call *0x10018,内核的第一条指令是movw $0x1234,0x472。
  3. 内核的第一条指令位于0x10000c。
  4. 引导从程序头部表中得到段的数目以及每个段的大小,以此决定要从磁盘上读出多少个扇区。

加载内核

本部分主要需要了解.text段.rodata段和.data段,并且使用objdump读取ELF格式的信息。

boot/Makefrag文件中指定了引导的text段的位置为0x7c00。

练习4:
阅读并学习关于C语言指针的知识。下载pointer.c,编译运行并确保理解它。

pointer.c的代码和解释如下:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <stdio.h>
#include <stdlib.h>

void f(void) {
int a[4]; // 含有4个元素的整形数组
int *b =
malloc(16); // 分配16个字节的内存,并且用一个整形指针指向内存首地址
int *c; // 一个悬挂的整形指针
int i; // 一个整形数

printf("1: a = %p, b = %p, c = %p\n", a, b, c);
// 打印a和b和c的地址,分别为0xff9bebcc, 0x566fc160和0xf7ede1e8

c = a;
// 令c指向数组a的首地址
for (i = 0; i < 4; i++) a[i] = 100 + i; // 为a[0]到a[3]分配100-103
c[0] = 200; // 将c[0]也就是a[0]改为200
printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
a[3]);
// 输出200 101 102 103

c[1] = 300; // 将c[1]也就是a[1]改为300
*(c + 2) = 301; //将*(c + 2)也就是a[2]改为301
3 [c] = 302; // 将3[c]也就是c[3]改为302
printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
a[3]);
// 输出200 300 301 302

c = c + 1; // 令c指向a[1]
*c = 400; // 将a[1]改为400
printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
a[3]);
// 输出200 400 301 302

c = (int *)((char *)c + 1);
// 将c先转换为char指针指向下一个字节后再转回int指针
// 现在a数组的字节分布为(小端)C8000000 90010000 2D010000 2E010000
| (c的指针)*c = 500;
// 执行后的a数组字节分布(小端)C8000000 90F40100 00010000 2E010000
printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n", a[0], a[1], a[2],
a[3]);
// 输出200 128144 256 302

b = (int *)a + 1;
// 将b指向a[1]
c = (int *)((char *)a + 1);
// 将a先转换为char指针指向下一个字节后再转回int指针
printf("6: a = %p, b = %p, c = %p\n", a, b, c);
// 输出0xff9bebcc, 0xff9bebd0和0xff9bebcd
}

int main(int ac, char **av) {
// 函数入口
f();
return 0;
}

练习5:
修改了text段的加载地址使得汇编代码中的跳转地址出现错误,进而导致整个引导因为错误提前终止。

练习6:
结果是非常显然的,因为引导的作用就是将内核从磁盘加载进入内存中。使用objdump -h obj/kern/kernel可以看到如下的信息:
0 .text 00001809 f0100000 00100000 00001000 2**4
CONTENTS, ALLOC, LOAD, READONLY, CODE
可以直到内核的text段会被加载至内存中0x100000(物理地址)处。

第三部分 内核

使用虚拟内存去解决位置依赖

可以发现内核将自己链接至了非常高的虚拟地址,比如0xf0100000,为了将处理器虚拟地址的较低部分给用户程序去使用。将在下一个实验介绍这一现象。

实际上,许多的机器在物理内存中并没有0xf0100000这样的高地址。实际上由处理器的内存管理硬件将虚拟地址0xf0100000映射到了实际内存中的物理地址0x100000。

这涉及了分页机制以及页表。
在kern/entry.S设置CR0_PG标记之前,内存引用被当做线性地址。实际上,由于在boot/boot.S设置了线性地址到物理地址的一致映射,所以线性地址在这里可以等同于物理地址。
当CR0_PG标记被设置了之后,所有的内存引用都被当作虚拟地址。虚拟地址通过虚拟内存硬件被翻译成物理地址。
kern/entrypgdir.c将0xf0000000到0xf0400000的虚拟地址翻译为物理地址的0x000000到0x400000,也将0x00000000到0x00400000的虚拟地址翻译为物理地址的0x00000000到0x00400000。
引用这些地址范围以外的虚拟地址将会抛出缺页的异常。
但是还没有为该异常设置中断处理程序。这会导致QEMU导出机器状态并退出。

练习7:
在movl %eax, %cr0指令(启动页表)之前,0x00100000出的内存不为空,0xf0100000出的内存全为0。
当stepi之后,0xf0100000处的内存和0x00100000处的内存完全一样。这表明已经成功启用了页表,并且完成了地址的映射。

控制台的格式化字符串

练习8:
缺失的代码为:

1
2
3
4
case 'o':
num = getuint(&ap, lflag);
base = 8
goto number;

  1. console.c提供了基本的I/O操作,同时封装了cputchar、getchar等函数供printf.c中的printf使用。printf使用了vprintfmt去解析格式化字符串并提供可变参数的特性。
  2. 这段代码主要实现了换行。其首先检查了当前的光标是否超过了最大值,如果是,则证明需要进行换行。其将第1行到第MAX-1行的内容复制到第0行到第MAX-2行所在的内存中,然后将第MAX-1行置空。最后将光标设置到新一行的开始。
  3. fmt指向了格式化字符串”x %d, y %x, z %d\n”
    ap指向了局部变量并且初始值为1
    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
    vcprintf(0xf0102449, 0xf0110e14);
    0xf0102449 -> "x %d, y %x, z %d\n" 0xf0110e14 -> 1
    cons_putc(120);
    cons_putc(32);
    va_arg(0xf0110dbc, int);
    Before: 0xf0110dbc -> 0xf0110e14 -> 1
    After: 0xf0110dbc -> 0xf0110e18 -> 3
    cons_putc(49);
    cons_putc(44);
    cons_putc(32);
    cons_putc(121);
    cons_putc(32);
    va_arg(0xf0110dbc, int);
    Before: 0xf0110dbc -> 0xf0110e18 -> 3
    After: 0xf0110dbc -> 0xf0110e1c -> 4
    cons_putc(51);
    cons_putc(44);
    cons_putc(32);
    cons_putc(122);
    cons_put(32);
    va_arg(0xf0110dbc, int);
    Before: 0xf0110dbc -> 0xf0110e1c -> 4
    After: 0xf0110dbc -> 0xf0110e20 -> 536870922
    cons_put(52);
    cons_put(10);
    注意这里va_arg是宏而不是函数,不能通过加断点的方式跟踪。我采用的方法是在调用va_arg的地方添加断点并跟踪。
    在GNUmakefile中的C_FLAGS -O1会重排C代码,导致了追踪va_arg变得困难。所以,仅在此处将-O1变成-O0,尽管这会导致在backtrace时kernel panic。
  4. 57616 = 0xe110。此外,根据x86的小端序,&i指向了byte序列0x72、0x6c、0x64、0x00。这等同于字符串”rld”。所以,最终的输出为”He110 World”。
    需要将i改为0x726c6400。不需要修改57616。
  5. 这是由于程序从格式化字符串中推断出了应当有3个参数,所以程序会从cprintf的栈中多读取一个参数。但实际上只有2个参数。所以最后一个参数是未指定的。
  6. vcprintf(…, const char * fmt)。

练习9:
f0100034: bc 00 00 11 f0 mov $0xf0110000,%esp
这一条指令初始化了引导栈,它位于0xf0110000处。内核仅通过设置esp寄存器的值为栈预留空间。栈指针指向高地址,并且栈自高地址向低地址延伸。

练习10:
本题考察了x86架构下的栈帧与函数调用。
函数调用时先将返回地址压栈,然后跳转至目标函数的起始地址;在目标函数内先将ebp寄存器的值(栈底)压栈保存,然后再将栈顶指针设置为新的栈底;
在函数中调用函数需要使用栈来传递参数,即将函数的参数以此压入栈中;
test_backtrace函数的汇编中使用了ebx寄存器,该寄存器为被调用者保存的寄存器,在使用的时候也要先压栈保存,再函数返回时恢复;
函数返回的时候通过先操作esp释放栈资源,然后恢复相应的被调用者保存的寄存器的值,最后调用汇编指令leave、ret返回;
leave指令先将esp的值置为ebp,然后再从栈中取出被保存的ebp的旧值;ret从栈中取出返回地址并跳转。

练习10-12:
mon_backtrace的实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int mon_backtrace(int argc, char **argv, struct Trapframe *tf) {
uint32_t ebp, eip, args[5];
struct Eipdebuginfo info;
cprintf("Stack backtrace:\n");
for (ebp = read_ebp(); ebp != 0; ebp = *((uint32_t *)ebp)) {
eip = *((uint32_t *)ebp + 1);
debuginfo_eip(eip, &info);
args[0] = *((uintptr_t *)ebp + 2);
args[1] = *((uintptr_t *)ebp + 3);
args[2] = *((uintptr_t *)ebp + 4);
args[3] = *((uintptr_t *)ebp + 5);
args[4] = *((uintptr_t *)ebp + 6);
cprintf(" ebp %08x eip %08x args %08x %08x %08x %08x %08x\n", ebp,
eip, args[0], args[1], args[2], args[3], args[4]);
cprintf(" %s:%d: %.*s+%d\n", info.eip_file, info.eip_line,
info.eip_fn_namelen, info.eip_fn_name, eip - info.eip_fn_addr);
}
return 0;
}

查阅STABS文档可以知道表示行号的成员是n_desc,所以debuginfo_eip的缺失的代码如下:
1
2
3
4
5
6
stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
if (lline <= rline) {
info->eip_line = stabs[lline].n_desc;
} else {
return -1;
}

修改后的commands结构体如下:
1
2
3
4
5
static struct Command commands[] = {
{ "help", "Display this list of commands", mon_help },
{ "kerninfo", "Display information about the kernel", mon_kerninfo },
{ "backtrace", "Display information about the stack frames", mon_backtrace },
};

提高 - 允许控制台输出不同颜色的文本

要求能增强控制台的功能使得控制台可以输出不同颜色的字体。这里使用了传统的实现,解析嵌入在文本字符串中的ANSI转义序列来实现题目的要求。

在王爽的《汇编语言》中,已经接触过了字符的“属性字节”,一个字符的自低到高的第2个字节可以作为属性字节,用来指示字符的属性如闪烁、高亮、前景色、背景色等。
有关于ANSI转义序列的相关知识可以参考这里

出于简化考虑,只部分实现ANSI转义序列中的ESC[Ps;...;Psm

实现的思路是实现<kern/printf.c>中的punch函数的替代版本attribute_punch,来实现对于ANSI转义序列的解析,并且相应地设置字符的属性字节。

解析所需要的状态机具有三个状态:A_NORM代表正常的输出字符的状态、A_TRANS代表接收到[ESC]开始,从正常状态到解析转义序列的过渡状态、A_ESCAPE代表解析转义序列的状态。它们之间的状态转换图如图所示:

value用来存储每一个解析到的值,temp代表了解析过程中临时的属性字节,attribute代表了当前打印字符时附加的属性字节。

具体的实现代码在<kern/printf.c>中:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// state for ANSI escape sequence interpretation
enum { A_NORM = 0, A_TRANS, A_ESCAPE };

// colormap - number (x - 30/40)[0, 7] -> attribute byte
static uint16_t colormap[8] = {
0x0000, 0x4400, 0x2200, 0x6600, 0x1100, 0x5500, 0x3300, 0x7700,
};

static void attribute_punch(int ch, int *cnt) {
static int value = 0; // value
static int state = A_NORM; // current state
static int temp = 0x0000,
attribute = 0x0000; // temp attribute, current attribute

switch (state) { // state machine
case A_NORM:
if (ch == 0x1B) { // [ESC]
state = A_TRANS; // transfer from A_NORM to A_TRANS
} else {
cputchar((attribute & 0xFF00) |
ch); // put character with attribute
*cnt++;
}
break;
case A_TRANS:
if (ch == '[') { // [
state = A_ESCAPE; // transfer from A_TRANS to A_ESCAPE
} else {
state = A_NORM; // transfer from A_TRANS to A_NORM
}
break;
case A_ESCAPE:
if (ch >= '0' && ch <= '9') { // digit - update value
value = value * 10 + ch - '0';
} else if (ch == ';' ||
ch == 'm') { // ; or m set temp and clear value
if (value == 0) {
temp = colormap[0];
} else if (value == 5) {
temp |= 0x8000;
} else if (value >= 30 && value <= 38) {
temp |= colormap[value - 30] &
0x0700; // look up in color map
} else if (value >= 40 && value <= 48) {
temp |=
colormap[value - 40] & 0x7000; // avoid complex cases
}
value = 0;
if (ch == 'm') { // m needed extra work - update attribute
attribute = temp;
temp = 0x0000;
state = A_NORM; // transfer from A_ESCAPE to A_NORM
}
} else { // non_digit nor m
state = A_NORM; // transfer from A_ESCAPE to A_NORM
}
break;
}
}

int vcprintf(const char *fmt, va_list ap) {
int cnt = 0;

// vprintfmt((void*)putch, &cnt, fmt, ap);
// use attribute_punch rather than punch
vprintfmt((void *)attribute_punch, &cnt, fmt, ap);
return cnt;
}

最后在monitor.c中添加相关cprintf代码,并重新编译测试。最终如图所示:

有关于实验指导中提到的打开vga硬件的graphics mode使得控制台绘制文本到图形帧缓冲区的实现,由于时间和难度原因,这里暂时跳过。

实验小结

最终执行make grade,评分脚本的输出如下:

1
2
3
4
5
6
7
running JOS: (1.2s)
printf: OK
backtrace count: OK
backtrace arguments: OK
backtrace symbols: OK
backtrace lines: OK
Score: 50/50

至此,实验一结束。

第一个实验总体来说更偏重于概念的理解、工具的使用而不是实际的代码。

尽管如此,大量的概念也浪费了我很多时间去理解。MIT的6.828同清华的ucore操作系统实验相比提供了相当多的reference(ucore的阅读材料几乎都是现成的),这也对文档阅读和信息检索能力有了更高的要求。

评论和共享

域名变更说明

发布在 通知

域名信息

  1. 2016年1月3日,域名duskdragon.com随阿里云学生主机一起购入,预计于2017年1月3日过期
  2. 2016年2月1日,域名duskdragon.com备案完成
  3. 2016年11月6日,域名duskdragon.com续费1年,预计于2018年1月3日过期
  4. 2017年11月20日,新域名codedragon.tech购入,预计于2022年11月21日过期

域名变更说明

从即日起至2018年1月3日,旧域名duskdragon.com和新域名codedragon.tech将同时有效,可通过这两个域名中的任意一个的二级域名blog访问本博客。

从2018年1月4日起,旧域名duskdragon.com将完全废弃,仅可通过codedragon.tech的二级域名blog访问本博客。

本次域名变更主要为了使域名更加贴近码龙的设定,并且在相当长的一段时间内都将会维持稳定;次要的考量在于.com域名的相对高价格。

由于codedragon.com已被注册,所以退而求其次地选择了codedragon.tech作为新域名。

博客更新说明

本次域名更新的同时也对博客进行了更新

  1. 更换了新的头像 - Character(c) 我/Art By 漫步
  2. 博客描述性文字的修改
  3. 如果不额外说明,本博客的所有文章默认以CC BY-NC-SA 4.0即署名-非商业性使用-相同方式共享4.0国际发布。有关该协议的概要可以参考这里
  4. 修复了失效的友情链接并添加了Suncio的博客为友情链接

评论和共享

实验答案托管在我的GitHub

Cache Lab的Part B是我卡了比较久的实验,在7月份做完Part A之后我卡在了Part B的第二个矩阵优化,之后进度一直缓慢。直到几天之前团队分享,我才把这个实验重新捡了回来,最终将第二个矩阵转置优化到了1500+的miss数(尽管仍然没有达到满分),后参考了网上的思路完成了Part B,总结如下。

实验简介

Cache Lab - Understanding Cache Memories主要是有关缓存的实验,对应于书本的第6章:存储器层次结构。主要阐明了缓存对于C语言程序的性能影响。

本实验的第二部分要求优化一个简单的矩阵变换函数,使其具有尽可能晓得缓存不命中数。

关于本实验的具体介绍详见实验讲义

实验要求 - Part B

在Part B中你需要在trans.c中写一个矩阵转置函数,该函数要能有尽可能少的缓存不命中(miss)数。

令A代表一个矩阵,A(i, j)代表矩阵A的第i行第j列的元素。
那么,令B为矩阵A的转置,则对于A中的任意一个元素,满足A(i, j) = B(j, i)。

一个朴素的矩阵转置函数如下:

1
2
3
4
5
6
7
8
9
10
11
void trans(int M, int N, int A[N][M], int B[M][N]) {
int i, j, tmp;

for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
tmp = A[i][j];
B[j][i] = tmp;
}
}

}

该函数是正确的,但却并不是高效的,因为其访问模式导致了相当多的缓存不命中。

你的任务是完成一个相似的函数,并对于不同大小的矩阵块(32×32,64×64,61×67),最小化该函数的缓存不命中数。

对于Part B有以下的要求和限制:

  1. 你所写的程序在编译时不能有任何的警告
  2. 在每一个你所写的转置函数中,你最多只能定义12个int型的局部变量
  3. 你不能使用long型的变量或是使用任何的技巧来使得在一个变量中存入多余一个的值
  4. 你的转置函数不能使用递归
  5. 如果你使用辅助函数,那么在同一时刻,你的调用栈上也不能出现超过12个局部变量
  6. 你的转置函数不能修改矩阵A,但是,你能任意的修改矩阵B
  7. 你不能定义任何的数组或是任何使用malloc的变量

实验过程 - Part B

缓存简介

局部性

局部性分为时间局部性和空间局部性——在一个具有良好的时间局部性的程序中,被引用过一次的内存位置可能在不远的将来再被多次引用。在一个具有良好的空间局部性的程序中,如果一个内存位置被引用了,那么程序很可能在不远的将来引用附近的一个内存位置。

一般来说,有良好局部性的程序比局部性差的程序运行的更快。现代计算机系统的各个层次,设计都利用了局部性。

在硬件层,通过高速缓存存储器来保存最近被引用的代码和数据,提高对主存的访问速度。
在操作系统层面,将虚拟内存作为主存和磁盘间高速缓存。
在网络中,主机可以作为代理缓存经常被访问的网页,浏览器也可以缓存最近访问过的页面。

存储器层次结构

我们可以依次地组织不同的存储器,形成一个典型的存储器层次结构。如下图所示。

在该结构中,自高层向底层走,存储设备变得更慢、更便宜和更大。每一层的存储器都作为下一级存储器的缓存。

高速缓存

早期的计算机系统的存储器结构只有3层:CPU寄存器、DRAM主存储器和磁盘存储。随着CPU和主存之间不断加大的差距,系统设计者被迫在寄存器文件和主存之间加入了一个小的SRAM高速缓存处理器,称为L1高速缓存(一级缓存),L1高速缓存的访问速度几乎和寄存器一样快,典型地是约4个时钟周期。

随着CPU和主存之间的性能差距进一步增大,系统设计者在L1缓存和主存之间又加入了一个更大的高速缓存,称为L2高速缓存,可以在约10个时钟周期内被访问到。

有些现代系统还包括有一个更大的高速缓存,称为L3高速缓存,它位于L2高速缓存和主存之间,可以在大约50个时钟周期内被访问到。

组织结构

假定一个计算机系统,其每个存储器地址为m位,那么形成了M = 2 ^ m个不同的地址。

这样一个机器的高速缓存被组织成一个有S = 2 ^ s个高速缓存组(Cache Set)的数组,每个组包含E个高速缓存行(Cache Line)。每个行是由一个B = 2 ^ b字节的数据块(Block)组成的,一个有效位(valid bit)指明这个行是否包含有意义的信息。t = m - (b + s)个标记位(tag bit),它们唯一地标识存储在这个高速缓存行中的块。

一个通用的高速缓存组织结构可以用元组(S, E, B, m)来描述。
高速缓存的大小C指的是所有块(不包括标记位和有效位)的大小的和,C = S × E × B。

一个m位的地址L被组织为3个部分,分别是高t位的标记位,中间s位的组索引以及低b位的块偏移。

L中的s个组索引是一个到S个组的数组的索引,从0开始。其指示了该地址所指示的字应当存储到哪个组中。
L中的t个标记位指明了该组中的哪一行包含这个字。当且仅当有效位为1且行的标记位与地址的标记位相同时,组中的行才包含了这个字。
块偏移b指明了在B个字节的数据块中的字偏移。

分类

根据每个组的高速缓存行数E,高速缓存被分为不同的类:

  • 直接映射高速缓存。直接映射高速缓存中每个组只有一行(E = 1)。
  • 组相连高速缓存。组相连高速缓存放宽了直接映射高速缓存中每个组只有一行的限制(1 < E < C/B)。
  • 全相连高速缓存。全相连高速缓存是由一个包含了所有高速缓存行的组(E = C/B)组成的。

组相连高速缓存引入了不命中时行替换策略的问题。比较常见的策略有最不常使用(LFU)和最近最少使用(LRU)。

由于构造又大又快的相连高速缓存很困难,全相连高速缓存通常只适合做小的高速缓存,如TLB(翻译备用缓冲器)。

高速缓存写

高速缓存写分为直写和写回。

  • 直写,当缓存更新后立刻将相应的高速缓存块写回到下一层存储器中。直写的缺点在于每次写都会引起总线流量。
  • 写回,尽可能地推迟更新,只有当替换算法需要驱逐更新过的块时,才执行写入操作。写回极大地降低了总线流量。但是高速缓存必须对于每一个高速缓存行维护一个额外的修改位(dirty bit)来表明这个高速缓存块是否会修改过。

实验思路

首先要明确,尽管矩阵的转置本身导致对于A矩阵(原始矩阵)的读和B矩阵(转置矩阵)的写不可能同时为连续的(即不可能同时存在连续读和连续写——对A矩阵行的连续读必然导致对B矩阵列的非连续写)。
但只要矩阵的大小小于缓存的总大小,那么在理想的情况下,在最初的强制不命中(即缓存为空导致的不命中)后,整个矩阵都会被加载进入缓存。在这之后的所有对于B矩阵的不连续写的引用都会命中。

在该实验中,缓存采用的是直接映射高速缓存,s = 5,b = 5,E = 1。对于该缓存,总共存在32个组,每个组共32个字节,可以装入8个int型变量,是非常有限的缓存,主要需要解决以下两个问题:

  1. 直接映射缓存所带来的冲突不命中。观察程序中矩阵存储的位置即可以发现,矩阵A和矩阵B的同一行实际上被映射到了同一个缓存组。当进行对角线的引用时,一定会发生缓存的冲突不命中。需要仔细地处理对角线上的元素。
  2. 所需优化的矩阵的总大小超出了缓存的总大小。必然导致程序的访存效率低下。

为了解决第一个问题,我们需要仔细地考虑对于矩阵元素访问的顺序。至于第二个问题,我们采用矩阵的分块技术来降低不命中数。

矩阵分块的目的在于将大的、不能完全加载进入缓存的大矩阵分块成小的、可以完全加载进入缓存的小矩阵块来处理。小矩阵块具有良好的局部性,性能显著增加。
但同时也要注意,分块使得程序的可阅读性大大降低,因此一般只在常用的库函数中采用分块优化。

第一部分 32 × 32矩阵优化

第一部分满分的要求是300个misses以内,misses超过600则0分。

首先对矩阵进行分块处理。为了完全利用每一个缓存快(32个字节)采用8 × 8分块。然后处理对角线的问题。这里我采用的方法是无论是哪一个矩阵分块,均从该矩阵分块的对角线开始处理。同时对于A矩阵(原始矩阵)按列优先(不连续读),对于B矩阵(转置矩阵)按行优先(连续写)。

通过优先处理对角线(a, a)的元素,保证了B矩阵的第a行被载入缓存中,接下来对于A矩阵的列优先处理保证了B矩阵的第a行缓存被充分利用。

对于32 × 32的矩阵,总共存在1024次读和1024次写。对于非对角线的分块(总共12个),其缓存不命中率是1/8(仅强制不命中),对于对角线的分块(总共4个),其写的缓存不命中率是1/8(强制不命中),其读的缓存不命中率为1/4(强制不命中和冲突不命中各一半)。

因此,理论上优化之后的总缓存不命中数为2048 × 0.75 × 0.125 + 1024 × 0.25 × 0.125 + 1024 × 0.25 × 0.25 = 288次。

第一部分优化之后的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
for (a = 0 ; a < N ; a += 8) {
for (b = 0 ; b < M ; b += 8) {
for (c = b ; c < b + 8 ; ++c) {
for (d = a + c - b ; d >= a ; --d) {
B[c][d] = A[d][c];
}
for (d = a + c - b + 1 ; d < a + 8 ; ++d) {
B[c][d] = A[d][c];
}
}
}
}

实际测试的缓存不命中数为287次,与理论值几乎一致。

第二部分 64 × 64矩阵优化

第二部分的满分要求是misses小于1300,当misses大于2000则零分。

第二部分对于misses的要求限制的非常严格,同时如果采用第一部分的8 × 8分块方式会出人意料地带来大量的misses。下面具体分析8 × 8分块导致misses增多的原因。

实验采用的缓存为直接映射高速缓存,s = 5, b = 5, E = 1。对于任意一个地址,其从低地址开始的第0-4位为块偏移b,第5-9为组索引s。

对于32 × 32的矩阵M来说,M[0][1]和M[1][1]之间总共间隔32个int型元素,也就是0x80个字节,也就是说,同一列相邻行的元素之间的地址间隔为0x80 = 0x100|00000。对于8 × 8的矩阵分块而言,其8行可以全部被加载进入缓存中而不发生任何冲突不命中。

然而,对于64 × 64的矩阵,其同一列相邻行的元素之间的地址间隔为0x100 = 0x1000|00000。对于8 × 8的矩阵分块而言,其第1、2、3、4行的元素会和第5、6、7、8行的元素占用相同的高速缓存组,进而出现严重的冲突不命中现象。

使用4 × 4的矩阵分块又无法充分利用每一个高速缓存行(32个字节=8个int数据),仍然无法达到所要求的misses数。

经过大量的尝试,我使用了以下的方法进行矩阵转置的优化:

仍然按照8 × 8对矩阵进行分块,只是在8 × 8的分块内部再按照4 × 4进一步分块,得到左上、右上、左下、右下4个子块。

紧接着依次按照左上、右上、右下、左下的方式处理4个子块(A矩阵)。
对于左上、右下这两个可能出现对角线元素的块,按照第一个矩阵优化的方式进行处理。
右上、左下子块不能简单地按照A矩阵不连续读,B矩阵连续写的方式处理。原因是对于对角线上的8 × 8分块来说,A、B矩阵的左上子块和右下子块占用了相同的高速缓存组,存在着严重的冲突不命中风险。
因此对于右上、左下的子块,我们按照下图的方式处理。

图中,上方的矩阵为矩阵A,下方的矩阵为矩阵B,小方块代表矩阵的元素,黑色方块的表明加载进入临时变量/已写入的元素。红色的线表明该行被缓存。

  1. 利用8个临时变量,将左上子块的前两行加载进入临时变量中,考虑到之前的缓存条件,该次加载的缓存命中。
  2. 将一个小的2×2的矩阵转置写入矩阵B右下子块的前两行,无论是否为对角线上的分块,该次写入一定会发生缓存不命中,同时将B矩阵的前两行载入高速缓存行。
  3. 将矩阵A左上子块的后两行的2×2的矩阵加载进入空闲的4个临时变量中,同之前加载相似,该次加载的缓存命中。
  4. 将刚刚加载的2×2矩阵转置写入B矩阵右下子块前两行的剩余位置,由于之前这两行已经加载进入了高速缓存行,故该次写入的缓存全部命中。
  5. 将矩阵A后两行的剩余元素加载进入空闲的4个临时变量中,缓存命中。
  6. 将8个临时变量中的元素依次转置写入矩阵B右下子块的最后两行中,同2相似,写入一定会发生缓存不命中,同时将矩阵B的后两行载入高速缓存行。

A矩阵左下子块的转置操作类似,这里不再赘述。

在A矩阵右上子块转置完成后,紧接着执行的是右下子块的转置,此时,对于非对角线上的分块而言,写入时的缓存必定命中。对于对角线上的分块,则会发生缓存不命中。

因此,对于64 × 64的矩阵,总共进行4096次读和4096次写,对于非对角线的分块(总共56个),对于A矩阵(原始矩阵而言),其左上、右下分块的不命中率为1/4,左下、右上分块的不命中率为0;对于B矩阵(转置矩阵而言),其左上、右上、左下分块的不命中率均为1/4,右下分块的不命中率为0。对于对角线上的矩阵,其B矩阵不命中率上升至1/4,对于A矩阵,其左上、右下的不命中率上升至1/2。

因此,理论上优化之后的总缓存不命中数为4096 × (8/64) × (1/2 × 1/4 + 0 × 1/4 + 0 × 1/4 + 1/2 × 1/4) + 4096 × (8/64) × 1/4 + 4096 × (56/64) × (1/4 × 1/4 + 0 × 1/4 + 0 × 1/4 + 1/4 × 1/4) + 4096 × (56/64) × (1/4 × 1/4 + 1/4 × 1/4 + 0 × 1/4 + 1/4 × 1/4) = 1376次。

该优化方法对应的代码如下:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
for (a = 0 ; a < M ; a += 8) {
for (b = 0 ; b < N ; b += 8) {
for (c = a ; c < a + 4 ; ++c) {
for (d = b + c - a ; d >= b ; -- d) {
B[c][d] = A[d][c];
}
for (d = b + c - a + 1; d < b + 4 ; ++d) {
B[c][d] = A[d][c];
}
}

tmp0 = A[b][a + 4];
tmp1 = A[b][a + 5];
tmp2 = A[b][a + 6];
tmp3 = A[b][a + 7];
tmp4 = A[b + 1][a + 4];
tmp5 = A[b + 1][a + 5];
tmp6 = A[b + 1][a + 6];
tmp7 = A[b + 1][a + 7];
B[a + 4][b] = tmp0;
B[a + 4][b + 1] = tmp4;
B[a + 5][b] = tmp1;
B[a + 5][b + 1] = tmp5;
tmp0 = A[b + 2][a + 4];
tmp4 = A[b + 2][a + 5];
tmp1 = A[b + 3][a + 4];
tmp5 = A[b + 3][a + 5];
B[a + 4][b + 2] = tmp0;
B[a + 4][b + 3] = tmp1;
B[a + 5][b + 2] = tmp4;
B[a + 5][b + 3] = tmp5;
tmp0 = A[b + 2][a + 6];
tmp4 = A[b + 2][a + 7];
tmp1 = A[b + 3][a + 6];
tmp5 = A[b + 3][a + 7];
B[a + 6][b] = tmp2;
B[a + 6][b + 1] = tmp6;
B[a + 6][b + 2] = tmp0;
B[a + 6][b + 3] = tmp1;
B[a + 7][b] = tmp3;
B[a + 7][b + 1] = tmp7;
B[a + 7][b + 2] = tmp4;
B[a + 7][b + 3] = tmp5;

for (c = a + 4; c < a + 8 ; ++c) {
for (d = b + c - a ; d >= b + 4 ; --d) {
B[c][d] = A[d][c];
}
for (d = b + c - a + 1 ; d < b + 8 ; ++d) {
B[c][d] = A[d][c];
}
}

tmp0 = A[b + 6][a];
tmp1 = A[b + 6][a + 1];
tmp2 = A[b + 6][a + 2];
tmp3 = A[b + 6][a + 3];
tmp4 = A[b + 7][a];
tmp5 = A[b + 7][a + 1];
tmp6 = A[b + 7][a + 2];
tmp7 = A[b + 7][a + 3];
B[a + 2][b + 6] = tmp2;
B[a + 2][b + 7] = tmp6;
B[a + 3][b + 6] = tmp3;
B[a + 3][b + 7] = tmp7;
tmp2 = A[b + 4][a + 2];
tmp3 = A[b + 4][a + 3];
tmp6 = A[b + 5][a + 2];
tmp7 = A[b + 5][a + 3];
B[a + 2][b + 4] = tmp2;
B[a + 2][b + 5] = tmp6;
B[a + 3][b + 4] = tmp3;
B[a + 3][b + 5] = tmp7;
tmp2 = A[b + 4][a];
tmp3 = A[b + 4][a + 1];
tmp6 = A[b + 5][a];
tmp7 = A[b + 5][a + 1];
B[a][b + 4] = tmp2;
B[a][b + 5] = tmp6;
B[a][b + 6] = tmp0;qizhongqizhong
B[a][b + 7] = tmp4;
B[a + 1][b + 4] = tmp3;
B[a + 1][b + 5] = tmp7;
B[a + 1][b + 6] = tmp1;
B[a + 1][b + 7] = tmp5;
}
}

实际测试的缓存不命中数是1379次。

到了这里我已经优化到了极限,但是依然没有达到满分,最后参考了网上的满分答案。
这里要注意到,实验讲义中说的很清楚,不允许修改矩阵A,但是矩阵B可以任意修改。因此,我们可以通过在矩阵B中暂存转置的结果来充分利用缓存,进一步降低缓存不命中数。思路如下图。

  1. 按行加载矩阵A,并且将其存入矩阵B。依次执行4次,直到整个分块的上半部分处理完毕。其中,每行的前4个元素被正确转置,后四个元素被暂存至矩阵B的右上分块。
  2. 对于分块的下半部分的第一行,先将矩阵B的右上分块的4个元素载入至临时变量,然后从矩阵A中的左下分块读取第一列并转置进入矩阵右上分块的第一行,然后将读出的4个元素存入矩阵B右下分块的第一行,最后再将矩阵A右下分块第一列转置送入矩阵B右下分块的第一行。
  3. 按照2的方式依次处理完下半部分的所有行。

对于一个8×8的分块而言,过程1处理了分块的上半部分,共执行了32次读和32次写。对于对角线上的分块,其读不命中率为1/8,写不命中率为1/4;对于非对角线上的分块,其读不命中率为1/8,写不命中率为1/8。过程2和3处理了分块的下半部分包括将矩阵B的右上子块移动到正确位置,将矩阵A的左下子块转置到B的右上子块以及矩阵A右下子块的转置,共执行了48次读和48次写。对于对角线上的分块,其读不命中率为1/3,写不命中率为1/4;对于非对角线上的分块,其读不命中率为1/12,写不命中率为1/12。

因此对于56个非对角线分块以及8个对角线分块,理论上优化后的总缓存不命中数为(32 × 1/8 + 32 × 1/8) × 56 + (32 × 1/8 + 32 × 1/4) × 8 + (48 × 1/12 + 48 × 1/12) × 56 + (48 × 1/3 + 48 × 1/4) × 8 = 1216次。

该优化方法的代码如下:

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
36
37
38
39
40
41
42
43
for (a = 0 ; a < N ; a += 8) {
for (b = 0 ; b < M ; b += 8) {
for (c = b ; c < b + 4 ; ++c) {
tmp0 = A[c][a];
tmp1 = A[c][a + 1];
tmp2 = A[c][a + 2];
tmp3 = A[c][a + 3];
tmp4 = A[c][a + 4];
tmp5 = A[c][a + 5];
tmp6 = A[c][a + 6];
tmp7 = A[c][a + 7];
B[a][c] = tmp0;
B[a + 1][c] = tmp1;
B[a + 2][c] = tmp2;
B[a + 3][c] = tmp3;
B[a][c + 4] = tmp4;
B[a + 1][c + 4] = tmp5;
B[a + 2][c + 4] = tmp6;
B[a + 3][c + 4] = tmp7;
}
for (c = a + 4 ; c < a + 8 ; ++c) {
tmp0 = B[c - 4][b + 4];
tmp1 = B[c - 4][b + 5];
tmp2 = B[c - 4][b + 6];
tmp3 = B[c - 4][b + 7];

B[c - 4][b + 4] = A[b + 4][c - 4];
B[c - 4][b + 5] = A[b + 5][c - 4];
B[c - 4][b + 6] = A[b + 6][c - 4];
B[c - 4][b + 7] = A[b + 7][c - 4];

B[c][b] = tmp0;
B[c][b + 1] = tmp1;
B[c][b + 2] = tmp2;
B[c][b + 3] = tmp3;

B[c][b + 4] = A[b + 4][c];
B[c][b + 5] = A[b + 5][c];
B[c][b + 6] = A[b + 6][c];
B[c][b + 7] = A[b + 7][c];
}
}
}

实际测试的缓存不命中数是1219次。

第三部分 61 × 67矩阵优化

由于61 × 67的矩阵不是方阵,不方便定量分析。同时限制放的比较宽松,满分misses小于2000,misses大于3000零分。因此无需考虑处理对角线,仅尝试换用不同的边长分块即可。16 × 16的分块已可以保证满分。

第三部分优化之后的代码如下:

1
2
3
4
5
6
7
8
9
for (a = 0 ; a < N ; a += 16) {
for (b = 0 ; b < M ; b += 16) {
for (c = b ; (c < b + 16) && (c < M) ; ++c) {
for (d = a ; (d < a + 16) && (d < N) ; ++d) {
B[c][d] = A[d][c];
}
}
}
}

实际测试的缓存不命中数是1847次。

实验结果

自动评分脚本给出的输出如下:

1
2
3
4
5
6
7
Cache Lab summary:
Points Max pts Misses
Csim correctness 27.0 27
Trans perf 32x32 8.0 8 287
Trans perf 64x64 8.0 8 1219
Trans perf 61x67 10.0 10 1847
Total points 53.0 53

实验总结

这次实验花费了我很久时间,最后还是参考了网上的解法并且花了很大精力去理解,实验给出的缓存条件非常苛刻,但同时也方便了定量分析。完成后确实大大加深了我对于缓存的理解。

这次实验中我认为比较重要/难的地方:一是对于缓存的理解以及矩阵元素在缓存中的排布问题;二是位于对角线上的分块不仅是内部而且在分块间存在的冲突不命中问题;三是虽然是矩阵,但是也要明确统一控制行列的变量。

评论和共享

实验答案托管在我的GitHub

这一个月一来一直在看《深入理解计算机系统》的后几章,终于全部看完了(除了第4章:处理器体系结构外)。然后开始集中处理实验,以下是Shell Lab的实验解答。

实验简介

Shell Lab - Writing Your Own Unix Shell主要是有关于进程、信号以及异常处理的实验,对应于书本的第8章:异常控制流。主要通过实现一个带作业控制的Unix Shell来熟悉进程以及信号的概念。

本实验已经给出了Tiny Shell的源程序的基本框架(tsh.c),你需要做的是填充该框架中的eval builtin_cmd do_bgfg waitfg sigchld_handler sigint_handler sigtstp_handler等函数。使得编译后的Shell具有相应的功能。

关于本实验的具体介绍详见实验讲义

Shell介绍

Shell是一个代表用户运行程序的命令行解释器。一个Shell周期性的打印一个提示符,从标准输入流等待一条命令行输入,然后根据命令行的输入执行相应的功能。

一条命令行输入是由空格分隔ASCII文本词(words)。命令行输入的第一个词要不然是一个内建命令(built-in command)要不然是一个可执行文件的路径。剩余的词是命令行参数。如果第一个词是内建命令,Shell立刻在当前进程中执行该命令。否则,词会被假设为一个可执行程序的路径。在这种情况下,Shell会fork出一个子进程,在子进程的上下文中加载并运行这个程序。被创建的子进程被称作任务(job)。总的来说,一个任务可以包含通过Unix管道(Unix Pipe)连接的多个子进程。

如果命令行输入以'&'结尾,那么这个任务将会在后台执行,这意味着Shell在打印下一个提示符并等待下一条命令行输入之前不会等待当前任务终止。在默认情况下,任务运行在前台,这意味这Shell在下一条命令行输入之前会等待当前任务终止。在任何的情况下, 只能有一个任务运行在前台,但是,可以有多个任务运行在后台。

例如,输入tsh> jobs使得Shell执行内建的jobs命令,输入tsh> /bin/ls -l -d则在前台运行ls程序,同时,这个程序的argc == 3,argv[0] == “/bin/ls”a,argv[1] == “-l”,argv[2] == “-d”。相应地,输入tsh> /bin/ls -l -d &则会在后台运行ls程序。

Unix Shell支持作业控制的概念,这允许用户将任务在前台和后台间来回移动,并且改变一个任务中进程的状态(运行,停止,终止)。按下ctrl-c将会发送SIGINT信号到当前前台任务的每一个进程中。按下ctrl-z将会发送SIGTSTP信号到前台任务的每一个进程中,SIGTSTP信号的默认功能是将进程设置为停止状态,直到其被一个SIGCONT信号唤醒。Unix Shell提供了不同的内建命令来支持作业控制,如:

  • jobs - 打印运行的和停止的后台任务
  • bg - 将一个停止的后台任务转变为一个运行的后台任务
  • fb - 将一个运行的或是停止的后台任务转变为一个运行的前台任务
  • kill - 终止一个任务

实验要求

所实现的tsh shell应当具有如下的特性:

  • 提示符应当为"tsh> "
  • 用户的命令行输入应当包括一个名字和0个或多个参数,均由一个或多个空格隔开。如果名字是一个内建命令,那么tsh应当立刻处理它并且等待下一个命令行输入。否则,tsh就会假设它是一个可执行文件的路径,并且在一个独立的子进程中加载并执行它
  • tsh不需要支持管道(|)和I/O重定向(>和<)
  • 按下ctrl-c(ctrl-z)将会导致一个SIGINT(SIGTSTP)信号被发送至当前的前台任务,如果现在没有前台任务,那么这些信号将没有效果
  • 如果命令行输入以一个'&'结束,那么tsh将会在后台运行这个任务,否则它会在前台运行这个任务
  • 每一个任务都可以被一个进程ID(PID)或是一个被tsh分配的正整数的任务ID(JID)唯一的标识。JIDS可以被前缀'%'标识,例如,'%5'就代表了JID 5,而'5'就代表了PID 5
  • tsh应当提供如下的内建命令:
    • quit命令直接终止shell
    • jobs命令列出所有在后台运行的任务
    • bg 命令通过给发送SIGCONT信号将其重启,然后将其在后台运行。参数既可以是一个PID,也可以是一个JID
    • fg 命令通过给发送SIGCONT信号将其重启,然后将其在前台运行。参数既可以是一个PID,也可以使一个JID
  • tsh应当回收它的所有僵死子进程。如果任何任务因为收到了一个未被捕获的信号而终止,那么tsh应当识别对应的事件并且输出相应的信息

实验评测

  1. 参考答案 - 实验提供了一个作为参考的tshref可执行文件作为tsh的参考。你的tsh应当提供和tshref一致的输出(除了PIDs以外)
  2. Shell驱动 - sdriver.pl程序将shell作为一个子进程来执行,根据trace file来向它发送命令和信号,并且将shell的输出捕获并输出。实验总共提供了16个trace file。关于sdriver的具体用法请参考实验讲义。

实验提供了tshref.out作为16个trace file在tshref程序下的参考输出。为了方便比较,写了一个小的(可能会有很多错误)的shell脚本gather_output.sh用来生成这些trace file在tsh下的输出,脚本如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin bash

output_file=tsh.out

echo "" > tsh.out

echo -e "\n" >> tsh.out

for trace_file in ./*.txt
do
echo -e "`./sdriver.pl -t $trace_file -s ./tsh -a "-p"`" >> tsh.out
done

echo -e "\n" >> tsh.out

实验思路

最早在做这个实验的时候一直没有什么头绪,即使已经参考了实验讲义,使用trace file来指导编程(trace file的难度自简单到复杂)。后来还是先好好的阅读了一遍给出的框架源代码,整理如下。

框架代码分析

描述
MAXLINE 定义了命令行1行允许的最大字符数 1024
MAXARGS 定义了命令行所允许的最大参数个数 128
MAXJOBS 定义了命令行同一时间允许的最多任务个数 16
MAXJID 定义了最大的任务ID 1<<16
UNDEF 未定义的状态 0
FG 任务运行在前台 1
BG 任务运行在后台 2
ST 任务停止 3

允许如下的状态转换
FG -> ST : ctrl-z
ST -> FG : fg命令
BG -> FG : fg命令
ST -> BG : bg命令

结构体

1
2
3
4
5
6
struct job_t {              //任务
pid_t pid; //任务的PID
int jid; //任务JID [1, 2, ...]
int state; //状态 - 包括UNDEF, BG, FG, ST
char cmdline[MAXLINE]; //对应的命令行输入
};

全局变量

变量名 变量类型 描述
environ char ** 定义在libc中 环境变量
prompt char[] 命令行提示符
verbose int 为1时输出额外信息
nextjid int 下一个待分配的JID
subf char[MAXLINE] 用于生成sprintf信息
jobs struct job_t [MAXJOBS] 全局任务表

函数列表

函数名 函数原型 描述
parseline int parseline(const char *cmdline, char **argv) 接收命令行输入以及参数列表,解析输入并且将解析到的参数存入参数列表,并且判断该命令是否以’&’结尾,是则返回1,否则返回0
sigquit_handler void sigquit_handler(int sig) SIGQUIT的信号处理函数
clearjob void clearjob(struct job_t *job) 将对应任务的PID,JID清零,状态设置为UNDEF,并且将命令行输入清空
initjobs void initjobs(struct job_t *jobs) 将任务列表中的所有任务清空
maxjid int maxjid(struct job_t *jobs) 返回任务列表中的最大JID
addjob int addjob(struct job_t jobs, pid_t pid, int state, char cmdline) 将给定任务添加至任务列表,如果nextjid超过了MAXJOBS,则将其重置为1
deletejob int deletejob(struct job_t *jobs, pid_t pid) 将对应任务从任务列表中删除,并将nextjid自增1
fgpid pid_t fgpid(struct job_t *jobs) 返回当前前台任务的PID,如果没有则返回0
getjobpid struct job_t getjobpid(struct job_t jobs, pid_t pid) 按照pid查询任务 如果没有则返回NULL
getjobjid struct job_t getjobjid(struct job_t jobs, int jid) 按照jid查询任务 如果没有则返回NULL
pid2jid int pid2jid(pid_t pid) 根据pid返回其jid,没有则返回0
listjobs void listjobs(struct job_t *jobs) 打印任务队列
usage void usage(void) 打印帮助信息
unix_error void unix_error(char *msg) 打印系统级错误信息并结束进程
app_error void app_error(char *msg) 打印应用级错误信息并结束进程
Signal handler_t Signal(int signum, handler_t handler) signal的包装函数
eval void eval(char *cmdline) 求值函数
builtin_cmd int builtin_cmd(char **argv) 处理内建函数
do_bgfg void do_bgfg(char **argv) 实现内建的bg和fg
waitfg void waitfg(pid_t pid) 等待前台的任务完成
sigchld_handler void sigchld_handler(int sig) SIGCHLD的信号处理程序
sigtstp_handler void sigtstp_handler(int sig) SIGTSTP的信号处理程序
sitint_handler void sigint_handler(int sig) SIGINT的信号处理程序

实验答案

为了简化篇幅,这里只附上几个相关的函数,已实现函数以及包装函数等就不一并附上。如有需要可以去GitHub中查看。

实验答案为我自己的实验解法,很可能不是最优解法,请不要直接抄袭。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
void eval(char *cmdline)
{
char * argv[MAXARGS];
char buf[MAXLINE];
int bg; /* if run in background */
pid_t pid;

sigset_t mask_all, mask_chld, prev_chld;

/*initialize signal sets*/
Sigfillset(&mask_all);
Sigemptyset(&mask_chld);
Sigaddset(&mask_chld, SIGCHLD);

strcpy(buf, cmdline);
bg = parseline(buf, argv); /* parse the command line */
if (argv[0] == NULL) {
return;
} /* handles if there is empty input */

if (!builtin_cmd(argv)) { /* if the command line is builtin command */
Sigprocmask(SIG_BLOCK, &mask_chld, &prev_chld); /* block SIGCHLD to avoid potential race between addjob and deletejob */
if ((pid = Fork()) == 0) {
Setpgid(0, 0); /* give the child process a new group id to handle SIGINT correctly */
Sigprocmask(SIG_SETMASK, &prev_chld, NULL); /* unblock SIGCHLD */
Execve(argv[0], argv, environ);
}
Sigprocmask(SIG_BLOCK, &mask_all, NULL); /* mask all signals to avoid potential races */
addjob(jobs, pid, bg + 1, cmdline); /* add job to joblist */
Sigprocmask(SIG_SETMASK, &prev_chld, NULL);
if (!bg) { /* if the process should be exeuted in foreground */
waitfg(pid); /* fg wait explictly */
} else {
printf("[%d] (%d) %s", pid2jid(pid), pid, cmdline); /* bg print message*/
}
}

return;
}

int builtin_cmd(char **argv)
{
/* handles the builtin command in current context */
if (!strcmp(argv[0], "quit")) {
exit(0); /* quit: exit directly*/
}
if (!strcmp(argv[0], "jobs")) {
listjobs(jobs); /* jobs: print the current job list */
return 1;
}
if (!strcmp(argv[0], "bg") || !strcmp(argv[0], "fg")) {
do_bgfg(argv); /* bg|fg: handles in function do_bgfg */
return 1;
}
if (!strcmp(argv[0], "&")) {
return 1; /* returns 1 for empty & */
}
return 0; /* not a builtin command */
}

void do_bgfg(char **argv)
{
int number = 0; /* used to store the converted number */
char * ptr = argv[1]; /* get the pointer to argument 1 */
char * endptr = NULL; /* used for error handling */
struct job_t * job = NULL; /* used to store job pointer */
if (!argv[1]) { /* returns if missing argument */
printf("%s command requires PID or %%jobid argument\n", argv[0]);
return;
}
if (*ptr == '%') { /* if argument 1 is job ID */
ptr++; /* adjust pointer */
number = strtol(ptr, &endptr, 10);
if (ptr == endptr) { /* handles convert error */
printf("%s: argument must be a PID or %%jobid\n", argv[0]);
return;
}
job = getjobjid(jobs, number); /* get the job */
if (!job) {/* handles if there is no such job */
printf("%%%d: No such job\n", number);
return;
}
} else {/* if argument 1 is pid */
number = strtol(ptr, &endptr, 10);
if (ptr == endptr) { /* handles convert error */
printf("%s: argument must be a PID or %%jobid\n", argv[0]);
return;
}
job = getjobpid(jobs, (pid_t)number); /* get the job */
if (!job) {/* handles if there is no such job */
printf("(%d): No such process\n", number);
return;
}
}
/* change process state and update the job list*/
if (!strcmp(argv[0], "bg")) { /*bg: turns ST to BG, send SIGCONT */
if(job->state == ST) {
Kill(-(job->pid), SIGCONT);
printf("[%d] (%d) %s", job->jid, job->pid, job->cmdline);
job->state = BG;
}
} else if (!strcmp(argv[0], "fg")) {/* fg: turns ST/BG to FG, sent SIGCONT */
if(job->state == ST) {
Kill(-(job->pid), SIGCONT);
job->state = BG;
}
if(job->state == BG) {
job->state = FG;
waitfg(job->pid);
}
}
return;
}

void waitfg(pid_t pid)
{
while(fgpid(jobs)) { /* handles all zombie processes in signal handler */
sleep(0.01); /* busy loop only */
}
return;
}

void sigchld_handler(int sig)
{
int olderrno = errno; /* store old errno */
int status; /* used to trace pid's status */
sigset_t mask_all, prev_all;
pid_t pid;

Sigfillset(&mask_all);

while((pid = Waitpid(-1, &status, WUNTRACED | WNOHANG)) > 0) { /* waitpid without waiting(WNOHANG) */
if (WIFSTOPPED(status) && (WSTOPSIG(status) == SIGTSTP || WSTOPSIG(status) == SIGSTOP)) { /* if the process is stopped */
struct job_t * job = getjobpid(jobs, pid);
if (job && job->state != ST) { /* if the stop signal hasn't been catched */
printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, WSTOPSIG(status));
struct job_t * stpjob = getjobpid(jobs, pid);
stpjob->state = ST;/* handles here */
}
}
if (WIFSIGNALED(status) && WTERMSIG(status) == SIGINT) { /* it the terminate signal hasn't been catched */
struct job_t * job = getjobpid(jobs, pid);
if (job) {
printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, WTERMSIG(status));
/* handles here */
}
}
if (WIFEXITED(status) || WIFSIGNALED(status)) {
Sigprocmask(SIG_BLOCK, &mask_all, &prev_all);
deletejob(jobs, pid);
Sigprocmask(SIG_SETMASK, &prev_all, NULL);
}/* remove the job in job list accordingly */
}
errno = olderrno;
return;
}

void sigint_handler(int sig)
{
int olderrno = errno; /* store old errno */
sigset_t mask_all, prev_all;
Sigfillset(&mask_all);
Sigprocmask(SIG_BLOCK, &mask_all, &prev_all); /* block all signal in case the race between SIGINT and SIGCHLD */

pid_t pid;
pid = fgpid(jobs);
Kill(-pid, SIGINT); /* kill processes in fg job's process group */

printf("Job [%d] (%d) terminated by signal %d\n", pid2jid(pid), pid, sig); /* print the message */

deletejob(jobs, pid); /* delete job in joblist */

Sigprocmask(SIG_SETMASK, &prev_all, NULL);

errno = olderrno;
return;
}

void sigtstp_handler(int sig)
{
int olderrno = errno; /* store old errno */
sigset_t mask_all, prev_all;
Sigfillset(&mask_all);
Sigprocmask(SIG_BLOCK, &mask_all, &prev_all); /* block all signal in case the race between SIGTSTP and SIGCHLD */

pid_t pid;
pid = fgpid(jobs);
Kill(-pid, SIGTSTP); /* send SIGTSTP to fg job's process group */

printf("Job [%d] (%d) stopped by signal %d\n", pid2jid(pid), pid, sig); /* print the message */

struct job_t * stpjob = getjobpid(jobs, pid);
stpjob->state = ST; /* modify the job list */

Sigprocmask(SIG_SETMASK, &prev_all, NULL);

errno = olderrno;
return;
}

实验总结

总的来说不难的一个实验,关键在于要先理解整个框架中的代码,然后根据trace file渐进地完成程序。需要注意的地方实验讲义中的提示以及书本中都已经给出,这里不再赘述。需要强调的是SIGCHLD的信号处理程序需要处理未捕获的SIGTSTP和SIGINT信号。此外SIGINT/SIGTSTP和SIGCHLD的信号处理程序之间可能会有潜在的导致错误的冲突。(信号处理程序是可以被其他信号中断的,可以见trace16.txt)

此外,handler中的printf是异步不安全的,不推荐使用。以及书本中虽然使用了sigsuspend来实行同步,但是为了简化程序,根据实验讲义的提示,使用了忙循环处理前台等待,并且将回收僵死进程任务交给了sigchld_handler。这些都是本次实验中不足和可以修改的地方。

评论和共享

实验答案托管在我的GitHub

由于Cache Lab的Part B的64 × 64的矩阵一直拿不到满分,索性放在了一边,先从老的Performance Lab开始做起。

实验简介

Performance Lab - Code Optimization是有关性能优化的实验,对应于书本的第5章:优化程序性能和第6章:存储器层次结构。主要提供了利用书本所学的知识优化代码的机会。

本实验主要分为两个部分,每个部分分别对于一个简单的图像处理函数进行优化。第一个部分所优化的函数旋转(rotate)对于缓存更加敏感,而第二个部分所优化的函数平滑(smooth)则属于计算密集型函数。对它们优化的侧重是有所不同的。

本实验的具体介绍见实验讲义

实验介绍

在本实验中,我们将实现两个图像处理函数——旋转和平滑。

我们将一张图片抽象地表示为一个二维矩阵M,M(i, j)代表了M中第i行第j列的像素的值,该像素值被定义为红色、绿色、蓝色(RGB)的值的三元组。在本实验中,我们只考虑正方形的图片。下标遵循C语言风格,从0到N-1。

旋转操作被定义为将图片逆时针旋转90°,旋转可以分为两步实现——

  1. 将矩阵转置,即将M(i, j)变为M(j, i)
  2. 将矩阵的第i行和第N - i - 1交换

平滑操作被定义为将每一个像素点的值换位周围像素点(以该像素点为中心的最多3*3的正方形)的平均值。

实验要求

在本实验中像素(pixel)是一个定义如下的结构体:

1
2
3
4
5
6
The core data structure deals with image representation. A pixel is a struct as shown below:
typedef struct {
unsigned short red; /* R value */
unsigned short green; /* G value */
unsigned short blue; /* B value */
} pixel;

此外,为了简化起见,还定义了如下的宏:

1
#define RIDX(i,j,n) ((i)*(n)+(j))

旋转操作的朴素版本如下:

1
2
3
4
5
6
7
void naive_rotate(int dim, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < dim; i++)
for(j=0; j < dim; j++)
dst[RIDX(dim-1-j,i,dim)] = src[RIDX(i,j,dim)];
return;
}

平滑操作的朴素版本如下(辅助函数未列出):

1
2
3
4
5
6
7
void naive_smooth(int dim, pixel *src, pixel *dst) {
int i, j;
for(i=0; i < dim; i++)
for(j=0; j < dim; j++)
dst[RIDX(i,j,dim)] = avg(dim, i, j, src); /* Smooth the (i,j)th pixel */
return;
}

为了简化起见,你可以假设所有的矩阵的边长都是32的倍数,并且在进行正确性测试的时候,只会测试5个值。

具体的注册函数和自动跑分机制请参阅实验讲义。

实验思路

旋转操作:旋转操作不涉及复杂的计算,经过测试将代码移动所带来的性能提升微乎其微。主要应当采用分块的手段提高代码的空间局部性的利用率。

平滑操作(平滑操作参考了别人的思路):平滑操作是计算密集型函数,经过测试,通过减少过程调用以及代码移动带来的有限的性能提升。
观察原始代码可以发现分支预测的惩罚是巨大的(因为循环只会执行3次,会带来大量的预测不命中)。我们可以考虑将红、绿、蓝三色的值的计算分开地并行处理,并且依次处理四个角、四条边、和剩余的像素点。以提升局部性的利用率并且降低分支预测不命中所带来的惩罚。

实验答案

旋转操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
void block_rotate(int dim, pixel * src, pixel * dst) {
int i, j, k, l;
int cst0 = dim - 1;
for (i = 0 ; i < dim ; i += 8) {
for (j = 0 ; j < dim ; j += 8) {
for (k = i ; k < i + 8 ; k++) {
for (l = j ; l < j + 8 ; l++) {
dst[RIDX(cst0 - l, k, dim)] = src[RIDX(k, l, dim)];
}
}
}
}
}

平滑操作:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void optimized_smooth(int dim, pixel * src, pixel * dst) {
int i, j;
int tmp;

dst[0].red = (src[0].red + src[1].red + src[dim].red + src[dim + 1].red) >> 2;
dst[0].green = (src[0].green + src[1].green + src[dim].green + src[dim + 1].green) >> 2;
dst[0].blue = (src[0].blue + src[1].blue + src[dim].blue + src[dim + 1].blue) >> 2;
i = dim - 1;
dst[i].red = (src[i].red + src[i - 1].red + src[i + dim].red + src[i + dim -1].red) >> 2;
dst[i].green = (src[i].green + src[i - 1].green + src[i + dim].green + src[i + dim -1].green) >> 2;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + dim].blue + src[i + dim -1].blue) >> 2;
i = i * dim;
dst[i].red = (src[i].red + src[i + 1].red + src[i - dim].red + src[i - dim + 1].red) >> 2;
dst[i].green = (src[i].green + src[i + 1].green + src[i - dim].green + src[i - dim + 1].green) >> 2;
dst[i].blue = (src[i].blue + src[i + 1].blue + src[i - dim].blue + src[i - dim + 1].blue) >> 2;
i = i + dim - 1;
dst[i].red = (src[i].red + src[i - 1].red + src[i - dim].red + src[i - dim - 1].red) >> 2;
dst[i].green = (src[i].green + src[i - 1].green + src[i - dim].green + src[i - dim - 1].green) >> 2;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i - dim].blue + src[i - dim - 1].blue) >> 2;

for (i = 1 ; i < dim - 1 ; i++) {
dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i + dim].red + src[i + dim - 1].red + src[i + dim + 1].red) / 6;
dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i + dim].green + src[i + dim - 1].green + src[i + dim + 1].green) / 6;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue + src[i + dim].blue + src[i + dim - 1].blue + src[i + dim + 1].blue) / 6;
}
for (i = dim * (dim - 1) + 1 ; i < dim * dim - 1 ; i++) {
dst[i].red = (src[i].red + src[i - 1].red + src[i + 1].red + src[i - dim].red + src[i - dim - 1].red + src[i - dim + 1].red) / 6;
dst[i].green = (src[i].green + src[i - 1].green + src[i + 1].green + src[i - dim].green + src[i - dim - 1].green + src[i - dim + 1].green) / 6;
dst[i].blue = (src[i].blue + src[i - 1].blue + src[i + 1].blue+ src[i - dim].blue + src[i - dim - 1].blue+ src[i - dim + 1].blue) / 6;
}
for (j = dim ; j < dim * (dim - 1) ; j+= dim) {
dst[j].red = (src[j].red + src[j + 1].red + src[j - dim].red + src[j - dim + 1].red + src[j + dim].red + src[j + dim + 1].red) / 6;
dst[j].green = (src[j].green + src[j + 1].green + src[j - dim].green+ src[j - dim + 1].green + src[j + dim].green + src[j + dim + 1].green) / 6;
dst[j].blue = (src[j].blue + src[j + 1].blue + src[j - dim].blue + src[j - dim + 1].blue + src[j + dim].blue + src[j + dim + 1].blue) / 6;
}
for (j = 2 * dim - 1 ; j < dim * dim - 1 ; j += dim) {
dst[j].red = (src[j].red + src[j - 1].red + src[j - dim].red + src[j - dim - 1].red + src[j + dim].red + src[j + dim - 1].red) / 6;
dst[j].green = (src[j].green + src[j - 1].green + src[j - dim].green + src[j - dim - 1].green + src[j + dim].green + src[j + dim - 1].green) / 6;
dst[j].blue = (src[j].blue + src[j - 1].blue + src[j - dim].blue + src[j - dim - 1].blue + src[j + dim].blue + src[j + dim - 1].blue) / 6;
}

for (i = 1 ; i < dim - 1 ; i++) {
for (j = 1 ; j < dim - 1 ; j++) {
tmp = i * dim + j;
dst[tmp].red = (src[tmp].red + src[tmp - 1].red + src[tmp + 1].red + src[tmp - dim].red + src[tmp - dim - 1].red + src[tmp - dim + 1].red + src[tmp + dim].red + src[tmp + dim - 1].red + src[tmp + dim + 1].red) / 9;
dst[tmp].green = (src[tmp].green + src[tmp - 1].green + src[tmp + 1].green + src[tmp - dim].green + src[tmp - dim - 1].green + src[tmp - dim + 1].green + src[tmp + dim].green + src[tmp + dim - 1].green + src[tmp + dim + 1].green) / 9;
dst[tmp].blue = (src[tmp].blue + src[tmp - 1].blue + src[tmp + 1].blue + src[tmp - dim].blue + src[tmp - dim - 1].blue + src[tmp - dim + 1].blue + src[tmp + dim].blue + src[tmp + dim - 1].blue + src[tmp + dim + 1].blue) / 9;
}
}
}

实验总结

实验的第一部分对于缓存的要求不是很高,简单的分块可以带来很大的性能提升。

实验的第二部分实际上我是卡了比较久的,在发现减少过程调用和代码移动性能提升有限后我就卡住了,因为我发现似乎无法进行循环展开。实际上还是太生疏了,没有想到要分析性能瓶颈,最后参考了别人的答案,实际上看到了别人答案的一瞬间就豁然开朗了,但是在这之前完全没有想到会是分支预测的问题。还需要多加练习。

评论和共享

作者的图片

码龙黑曜

iOS开发者/计算机科学/兽人控


华中科技大学 本科在读


Wuhan, China