-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlab4.html
More file actions
627 lines (494 loc) · 30.3 KB
/
Copy pathlab4.html
File metadata and controls
627 lines (494 loc) · 30.3 KB
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
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
<!doctype html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes">
<style>
h1,
h2,
h3,
h4,
h5,
h6,
p,
blockquote {
margin: 0;
padding: 0;
}
body {
font-family: "Helvetica Neue", Helvetica, "Hiragino Sans GB", Arial, sans-serif;
font-size: 13px;
line-height: 18px;
color: #737373;
background-color: white;
margin: 10px 13px 10px 13px;
}
table {
margin: 10px 0 15px 0;
border-collapse: collapse;
}
td,th {
border: 1px solid #ddd;
padding: 3px 10px;
}
th {
padding: 5px 10px;
}
a {
color: #0069d6;
}
a:hover {
color: #0050a3;
text-decoration: none;
}
a img {
border: none;
}
p {
margin-bottom: 9px;
}
h1,
h2,
h3,
h4,
h5,
h6 {
color: #404040;
line-height: 36px;
}
h1 {
margin-bottom: 18px;
font-size: 30px;
}
h2 {
font-size: 24px;
}
h3 {
font-size: 18px;
}
h4 {
font-size: 16px;
}
h5 {
font-size: 14px;
}
h6 {
font-size: 13px;
}
hr {
margin: 0 0 19px;
border: 0;
border-bottom: 1px solid #ccc;
}
blockquote {
padding: 13px 13px 21px 15px;
margin-bottom: 18px;
font-family:georgia,serif;
font-style: italic;
}
blockquote:before {
content:"\201C";
font-size:40px;
margin-left:-10px;
font-family:georgia,serif;
color:#eee;
}
blockquote p {
font-size: 14px;
font-weight: 300;
line-height: 18px;
margin-bottom: 0;
font-style: italic;
}
code, pre {
font-family: Monaco, Andale Mono, Courier New, monospace;
}
code {
/*background-color: #fee9cc;*/
color: rgba(0, 0, 0, 0.75);
padding: 1px 3px;
font-size: 12px;
-webkit-border-radius: 3px;
-moz-border-radius: 3px;
border-radius: 3px;
}
pre {
display: block;
padding: 14px;
margin: 0 0 18px;
line-height: 16px;
font-size: 11px;
border: 1px solid #d9d9d9;
white-space: pre-wrap;
word-wrap: break-word;
}
pre code {
background-color: #fff;
color:#737373;
font-size: 11px;
padding: 0;
}
sup {
font-size: 0.83em;
vertical-align: super;
line-height: 0;
}
* {
-webkit-print-color-adjust: exact;
}
@media screen and (min-width: 914px) {
body {
width: 854px;
margin:10px auto;
}
}
@media print {
body,code,pre code,h1,h2,h3,h4,h5,h6 {
color: black;
}
table, pre {
page-break-inside: avoid;
}
}
</style>
<title>MIT JOS Lab 4 Report</title>
</head>
<body>
<h1>MIT JOS Lab 4 Report</h1>
<p><strong>YANG Weikun 1100012442</strong></p>
<p><em>UPDATE Mon 18th Nov:</em> Solved concurrency challenge using fine-grained locking</p>
<p>All exercises finished on Thu 10th Oct 22:30 UTC+0800</p>
<h2>Ex.1 Multiprocessor support</h2>
<p><code>mmio_map_region</code> in <code>kern/pmap.c</code> would map page-aligned physical memory at a very high address (0xFE000000) that VM from <code>KERNBASE</code> cannot reach (over 256MB), to virtual address reserved in <code>[MMIOBASE, MMIOLIM)</code>. I called <code>boot_map_region</code> with cache-disabled, write-through and kernel-write permissions.</p>
<hr />
<h2>Ex.2 Application Processor Bootstrap</h2>
<p>By Intel's convention, on a multiprocessor platform, only the one and only bootstrap processor (BP) is started by the BIOS. We must start up other existing processors (Application processors) to utilise SMP, by emitting <em>'Inter Processor Interrupt'</em>(IPI) to each and every other processor cores. Start up code for APs is in <code>kern/mpentry.S</code>, copied to a predefined memory location before sending IPI to APs. That memory page must not appear in <code>page_free_list</code>, so <code>page_init()</code> in <code>kern/pmap.c</code> is updated to fit the change.</p>
<h3>Q&A</h3>
<ol>
<li><em>Why is the macro <code>MPBOOTPHYS</code> necessary in kern/mpentry.S but not in boot/boot.S?</em>
<ul>
<li>code in <code>kern/mpentry.S</code> is linked and loaded together with all other parts of the kernel (except for the bootloader), however those instructions are copied at runtime to another physical location, so they have to discard all link/load-time assumptions. To obtain a specific physical address of a variable in relocated code & data, we need <code>MPBOOTPHYS</code>.</li>
</ul>
</li>
</ol>
<hr />
<h2>Ex.3, 4 Per-CPU State and Initialization</h2>
<p>First part, setup per-CPU kernel stacks in <code>mem_init_mp()</code>, <code>kern/pmap.c</code>.</p>
<ul>
<li><p>For CPU i, its kernel stack top is <code>KSTACKTOP - i * (KSTKSIZE + KSTKGAP)</code></p>
<pre><code> for (i = 0; i < NCPU; i++)
boot_map_region(kern_pgdir, KSTACKTOP - i * (KSTKSIZE + KSTKGAP) -KSTKSIZE,
KSTKSIZE, PADDR(percpu_kstacks[i]), PTE_W);
</code></pre></li>
</ul>
<p>Second part, setup per-CPU TSS in <code>trap_init_percpu()</code>, <code>kern/trap.c</code>.</p>
<ul>
<li>For CPU i, its TSS is <code>cpus[i].cpu_ts</code>, and the corresponding descriptor in GDT is <code>gdt[(GD_TSS0 >> 3)+i]</code></li>
</ul>
<p>Now when <code>jos</code> is started with <code>make qemu CPUS=4</code> it shows:</p>
<pre><code>6828 decimal is 15254 octal!
Physical memory: 66556K available, base = 640K, extended = 65532K
...
SMP: CPU 0 found 4 CPU(s)
SMP: CPU 1 starting
SMP: CPU 2 starting
SMP: CPU 3 starting
...
</code></pre>
<hr />
<h2>Ex.5 Locking</h2>
<p>The <em>Big Kernel Lock</em> is obtained at defined places:</p>
<ul>
<li>In <code>i386_init()</code> just before waking up other CPUs. This is to prevent other CPUs from acquiring the lock before bootstrap CPU finishes initialisation. This could happen earlier.</li>
<li>In <code>mp_main()</code>, where the APs are about to enter the scheduler for the first time.</li>
<li>In <code>trap()</code>, after user processes are trapped into kernel mode.</li>
</ul>
<p>Those 3 points all indicate the beginning of some <em>serious kernel work</em>, that operates sensitive data structures that need mutual-exclusion protection.</p>
<p>BKL is released just before <code>env_pop_tf</code>.</p>
<h3>Q&A</h3>
<ol>
<li><em>Why do we still need separate kernel stacks for each CPU despite the 'Big Kernel Lock'?</em>
<ul>
<li>Because, when a interrupt occurs in user mode, the CPU will push <code>EIP</code>, <code>CS</code> etc. on stack by hardware, without acquiring a lock. In case another CPU is running in kernel mode, the shared stack will be corrupted.</li>
</ul>
</li>
</ol>
<hr />
<h2>Challenge: Concurrency in Kernel</h2>
<p>The Linux Kernel, to support SMP, used <em>Big Kernel Lock</em> to serialise, until version <code>2.6.39</code> in 2011. What we are doing here in <code>joe</code> is quite similar. The kernel acquires a giant lock to prevent all forms of concurrency, so no modification is necessary for any of the kernel data structures. Now, I will replace the <em>Big Kernel Lock</em> mechanism with fine-grained locking that only lock little parts of the kernel, to embrace concurrency in kernel. It proved to be something actually <em>challenging</em>.</p>
<p>First, consider which parts of the current kernel will fail when operated concurrently (copied from the hint provided by MIT), and how exactly:</p>
<ol>
<li><strong>Page Allocator</strong>: <code>page_free_list</code> must be handled atomically.
<ul>
<li><p>Scenario 1A: kernel on CPU0 calls <code>page_alloc</code>, so does kernel on CPU1, CPU2 etc. They all believe <code>page_free_list</code> is not NULL, then took the first page on the list, then moved forward <code>page_free_list</code> by one. Now, they've allocated a page -- but they are holding the same page. Suppose <code>page_alloc</code>ed pages are inserted into different user processes, now those processes mystically shares a physical page they thought private.</p>
<pre><code> if ((page = page_free_list) == NULL)
goto page_alloc_end;
page_free_list = page_free_list->pp_link;
</code></pre></li>
<li><p>Scenario 1B: kernel on CPU0 calls <code>page_decref</code> wanting to get rid of a page. This page's <code>pp_ref</code> is <code>1</code>, so it should be put back on the free list. <code>page_decref</code> is actually a <code>read-modify-(test)-and-write</code> process. Suppose CPU0 has not commited the change then kernel on CPU1 comes in and tries to map this very page to somewhere else, CPU1 believes <code>pp_ref</code> is still one so it proceeds with mapping, while CPU0 later puts the page on free list.</p>
<pre><code> if (-- pp->pp_ref == 0)
...
</code></pre></li>
<li>There exists plenty more horrible scenarios.</li>
</ul>
</li>
<li><p><strong>Console Driver</strong>: The console driver (actually the CGA and Serial buffer) must be accessed one at a time.</p>
<ul>
<li>Scenario 2A: Two kernel instances both call <code>cprintf(...)</code> to deliver some information. Since <code>cprintf</code> outputs one character at a time, we might see two messages intermixed.</li>
<li>Scenario 2B: Two kernel instances both call a series of <code>cons_getc()</code>. A complete sentence may be split into pieces when it hits those kernels' line buffers.</li>
</ul>
</li>
<li><p><strong>Scheduler</strong>: The scheduler considers the status of a process when deciding which one to run, it also posts modification on the status. Here's how it might fail.</p>
<ul>
<li>Scenario 3A: Two schedulers run at the same time. The first finds a process to load and run, but just before it could mark it <code>running</code>, the other scheduler picks the same process. Later this process may run simultaneously on two CPUs.</li>
<li>Scenario 3B: The parent process calls <code>sys_destroy</code> to kill one of its child, just before the child is marked <code>dying</code> or <code>free</code>, a scheduler picks this child process to run. Sadly <code>env_destroy</code> continues to free memory of a running process.</li>
<li>Scenario 3C: One process makes a system call. A scheduler managed to run the process before the completion of that system call.</li>
<li>This part of the kernel could go terribly wrong.</li>
</ul>
</li>
<li><strong>IPC states</strong>: When a process wants to receive a message, it may receive one and only one.
<ul>
<li>Scenario 4A: One process calls <code>sys_ipc_recv</code>, the kernel marks it receivable. Then many other processes call <code>sys_ipc_try_send</code> to the receiving process. They all believe that process wants their message, so memory could be mapped again and again, while the message value may get overwritten many times.</li>
</ul>
</li>
</ol>
<p>Apparently I'm not the first one to realise locks are used to lock <strong>data</strong>, not <strong>code</strong>. This is very important as such a tiny little kernel like <code>jos</code> may present very complicated code-paths, especially on multiple processors. We must focus on concurrency-sensitive data structures to avoid errors.</p>
<p>From those scenarios above, we conclude that there are so many data structures that must be protected:</p>
<ol>
<li><code>page_free_list</code>: since dereferencing a pointer and change it's value is quite difficult to be encapsulated as an atomic operation, I use a spin lock (<code>pm_lock</code>) to protect it. <code>pm_lock</code> is used in two places: <code>page_alloc()</code> and <code>page_free()</code></li>
<li><code>pp_ref</code> of every physical page: <code>pp_ref</code> is declared as an atomic variable, I used <code>atomic_inc</code> and <code>atomic_dec_test</code> to operate on it.</li>
<li>CGA buffer and Serial buffer: since we want calls to <code>cprintf</code> to be atomic (which means generally a sentence is not split into pieces), I used spin lock <code>cons_write_lock</code> inside <code>vprintfmt</code>. Note that <code>vprintfmt</code> is used in both kernel and user mode, only kernel mode requires locking (because user mode <code>cprintf</code> is buffered, and translates to kernel mode <code>vprintfmt</code>).</li>
<li>Keyboard and Serial input: the provided test programs for this lab did not use much of the input utility, and locking the input driver will require an input line buffer, so I did not implement locking here.</li>
<li>IPC states: IPC states are modified in two places, <code>sys_ipc_recv</code> and <code>sys_ipc_try_send</code>. Each user process has its own <code>env_ipc_lock</code>.</li>
<li>All other states of every user process <code>envs</code>: To make life easier, I use one big spin lock to protect the whole <code>envs</code> array. Protected data structures include: environments free list, environment status etc. And one atomic variable is used for every process to indicate whether they are in middle of an system call. In <code>env_run</code>, we must wait until the system call is finished before giving CPU to it.</li>
</ol>
<p>It all seems rather straight forward after my explanation, but the debugging process was not an pleasing experience.</p>
<ol>
<li>Operating Systems are generally considered un-debuggable, so <code>cprintf</code> is pretty much every thing you get. Running <code>jos</code> on <code>QEMU</code> that can talk to <code>GDB</code> is such a treasure, but still it's nothing like user space debugging. I really can't imagine how people are debugging the Linux kernel.</li>
<li>Reproducibility is an serious issue when timer interrupts comes in randomly, and <code>QEMU</code>'s SMP is not so consistent.</li>
<li>Concurrent programs are hard to debug, inheritedly.</li>
</ol>
<p>More on concurrency and synchronisation. For the sake of simplicity we used only spin locks (which are not recursive) and atomic variables (their implementation is strongly associated with architecture). And it's very nice that <code>jos</code>'s kernel is not preemptive.</p>
<p><strong>Important:</strong>
The <code>primes</code> and <code>pingpong</code> programs are perfect tests. Please do not be surprised with occasional warning messages coming out of the console, or very long periods of stall. The scheduler of <code>QEMU</code> isn't very stable. It sometimes prefers to run the CPU that is waiting for a lock, not the one that's holding the lock. And it seems that the emulated cache or memory is somehow inconsistent. Or maybe it's just my own fault.</p>
<p>I consulted <a href="http://lxr.free-electrons.com/">Linux Cross Reference</a> for implementation of atomic operations. And <em>Linux Kernel Development, 3rd edition by Robert Love</em> for general synchronisation in OS kernels.</p>
<hr />
<h2>Ex.6 Round-Robin Scheduling</h2>
<p>Before making this part of the lab work nicely, I had to write a fake timer interrupt handler in <code>trap_dispatch()</code>. Somehow timer interrupts are enabled.</p>
<p>For function <code>schedule_yield()</code>, we must check circularly in the <code>envs</code> array for the first <code>Env</code> with status of <code>ENV_RUNNABLE</code>, starting from <code>curenv</code> if it exists, or beginning of the array if not. If no candidate was found then <code>curenv</code> may be scheduled again. Then we call <code>env_run()</code> to drop to selected user program, or drop to <code>schedule_halt()</code> that shuts down the CPU. Next we need to dispatch <code>sys_yield</code> system call.</p>
<p>This is what I get on a 4-CPU system running 6 <code>user_yield</code> instances:</p>
<pre><code>[00000000] new env 00001000
...
[00000000] new env 00001005
Hello, I am environment 00001000.
Hello, I am environment 00001002.
...
Back in environment 00001000, iteration 0.
Back in environment 00001002, iteration 0.
Hello, I am environment 00001005.
Back in environment 00001001, iteration 0.
...
Back in environment 00001001, iteration 4.
Back in environment 00001004, iteration 3.
All done in environment 00001000.
...
[00001000] exiting gracefully
[00001000] free env 00001000
...
Back in environment 00001005, iteration 3.
...
All done in environment 00001004.
Back in environment 00001005, iteration 4.
[00001003] exiting gracefully
...
No runnable environments in the system!
</code></pre>
<h3>Q&A</h3>
<ol>
<li><em>Why can the pointer <code>e</code> be dereferenced both before and after the addressing switch?</em>
<ul>
<li>Most of the pointers used in kernel points to somewhere above <code>KERNBASE</code> (virtual mem), recall that all user memory spaces are identical to kernel memory space for VA above <code>KERNBASE</code>, therefore it is OK to address something in kernel space using a user environment's page directory.</li>
</ul>
</li>
<li><em>Whenever the kernel switches from one environment to another, it must ensure the old environment's registers are saved so they can be restored properly later. Why? Where does this happen?</em>
<ul>
<li>Such context switch, in our current Round-Robin scheduling, may happen only when:
<ul>
<li>A process gives itself up to the kernel by making the <code>yield</code> system call.</li>
<li>An interrupt of any other kind occurs. (For some cases the interrupted process may not resume)</li>
</ul>
</li>
<li>In both cases, process states are saved by our interrupt mechanism, details explained in the previous lab.</li>
</ul>
</li>
</ol>
<hr />
<h2>Ex.7 System Calls for Environment Creation</h2>
<p>There are 5 new system calls to be implemented, to support dumb fork (copy-on initilize).</p>
<ol>
<li><code>envid_t sys_exofork(void)</code> create a new <code>Env</code> using <code>env_alloc()</code>, set its status to <code>ENV_NOT_RUNNABLE</code> and copy the trap frame from the calling <code>Env</code> to this new <code>Env</code>. To later return <code>0</code> to the child, we must set <code>eax</code> register in the trap frame explicitly.</li>
<li><code>int sys_env_set_status(envid_t envid, int status)</code> find the <code>Env</code> with <code>envid</code>, and set it's status to <code>ENV_NOT_RUNNABLE</code> or <code>ENV_RUNNABLE</code>.</li>
<li><code>int sys_page_alloc(envid_t envid, void *va, int perm)</code> this one is slightly more complex. We must ensure the existence of <code>envid</code> and the validity of <code>va</code> and <code>perm</code>. Then we allocate a physical page and insert it into the <code>Env</code>'s VM.</li>
<li><code>int sys_page_map(envid_t srcenvid, void *srcva, envid_t dstenvid, void *dstva, int perm)</code> this is a syscall that copies memory mappings between different <code>Env</code>s. Like the previous one, but a lot more to verify. <code>page_lookup</code> is called to find the original mapping, then <code>page_insert</code> is called to setup the new mapping to the same physical location.</li>
<li><code>int sys_page_unmap(envid_t envid, void *va)</code> We use <code>page_remove</code> to do the job.</li>
</ol>
<p>Up to now all exercises of part A of lab4 is complete. My version of <code>jos</code> is now able to run <code>user/dumbfork</code> correctly (on 2 CPUs):</p>
<pre><code>[00000000] new env 00001000
[00001000] new env 00001001
0: I am the parent!
0: I am the child!
...
...
9: I am the parent!
9: I am the child!
[00001000] exiting gracefully
[00001000] free env 00001000
10: I am the child!
...
19: I am the child!
[00001001] exiting gracefully
[00001001] free env 00001001
No runnable environments in the system!
...
</code></pre>
<hr />
<h2>Ex.8 Setting the Page Fault Handler</h2>
<p>Implement <code>int sys_env_set_pgfault_upcall(envid_t envid, void *func)</code> to set the user mode page fault handler. The entry point of the handler is stored in <code>env->env_pgfault_upcall</code>.</p>
<h2>Ex.9 Invoking the User Page Fault Handler</h2>
<p>To invoke the user page fault handler we must modify <code>page_fault_handler</code> in <code>kern/trap.c</code>. This function first handles kernel mode page fault. It proceeds with calling the user mode page fault handler only when all of the following conditions are met:</p>
<ol>
<li>The user program has already registered a page fault up call by <code>sys_env_set_pgfault_upcall</code></li>
<li>The user program has already allocated a page of memory for the exception stack, from VA <code>UXSTACKTOP-PGSIZE</code> to <code>UXSTACKTOP-1</code>, and the mapping permits user write.</li>
<li>If the page fault happened while the user was processing a previous page fault, there must be enough space for the new handler's arguments on the exception stack. The stack must not overflow when new arguments are pushed.</li>
</ol>
<p>Otherwise, our kernel destroys this faulting user program.</p>
<p>In my implementation, I switched <code>CR3</code> to the page directory of the current user program to push arguments (a <code>struct UTrapframe</code>) on it's exception stack. Also if the trap-time user stack is the exception stack itself, another 4 bytes of space is reserved on stack before the arguments.</p>
<hr />
<h2>Ex.10, 11 User-mode Page Fault Entry Point</h2>
<p>The <code>_pgfault_upcall</code> routine in <code>lib/pfentry.S</code> is the one of the most sophisticated assembly code I've written in this lab. After the user defined <code>_pgfault_handler</code> returns, we must restore all general purpose registers, including stack pointer, instruction pointer and flags register to their trap-time state. The only way of transferring both control(<code>%eip</code>) and stack(<code>%esp</code>) back to the site that caused the page fault at the same time, is only achievable by pushing the trap-time <code>%eip</code> on trap-time stack, then call <code>ret</code> to hand over control. I would like to quote a bit of the code for clarity:</p>
<pre><code>_pgfault_upcall:
pushl %esp // function argument: pointer to UTF
movl _pgfault_handler, %eax
call *%eax // doing this because near jump does not support imm32
addl $4, %esp // pop function argument
addl $8, %esp // pop utf_fault_va and utf_err off the stack
movl 32(%esp), %eax // load the trap-time %eip to %eax
subl $4, 40(%esp) // decrease the trap-time %esp by 4, load to %ebx
// this is neccesary because i386 does not support `write to pointor in memory`
movl 40(%esp), %ebx
movl %eax, (%ebx) // store the trap-time %eip to (adjusted) trap-time stacktop
popal // restore the trap-time registers.
addl $4, %esp // pop the eip
popfl // restore eflags from the stack.
popl %esp // switch back to the adjusted trap-time stack.
ret // return to re-execute the instruction that faulted.
</code></pre>
<p><code>set_pgfault_handler</code> is much simpler, it allocates the exception stack if is called first, registers the user mode page fault handler using <code>sys_env_set_pgfault_upcall</code>.</p>
<p>Now my jos succeeds with <code>user/faultread</code>, <code>user/faultdie</code>, <code>user/faultalloc</code>, and <code>user/faultallocbad</code>.</p>
<hr />
<h2>Ex.12 Implementing Copy-on-Write Fork</h2>
<p>Things to do in <code>fork()</code> to support COW:</p>
<ol>
<li>Register parent process's page fault handler: <code>pgfault()</code> (later implemented).</li>
<li>Call <code>sys_exofork()</code> to create a new Env. Depending on the return value, code path splits:
<ul>
<li><code>sys_exofork()</code>'s return value is 0, we are the child process. Actually this system call will not return immediately in child like normal linux <code>fork</code> that might introduce race conditions, until the parent process explicitly sets the child's status, and the kernel reschedules. After <code>sys_exofork</code> returns we must fix <code>thisenv</code> to point to the right Env, since the old <code>thisenv</code> is inherited from the parent.</li>
<li><code>sys_exofork()</code>'s return value is a positive integer, which means that the system call succeeded and we are now in the parent process. Quite a lot of things to be done for the child process:
<ol type="a">
<li> First, scan through the parent process's virtual address space from <code>0</code> to <code>UXSTACKTOP-PGSIZE</code>, copy every existing mapping using <code>duppage()</code> (implemented later).</li>
<li> Allocate child's exception stack, by <code>sys_page_alloc</code>.</li>
<li> Register a page fault handler for the child using <code>sys_env_set_pgfault_upcall</code>. Here we cannot use the user mode function <code>set_pgfault_handler</code> because it can only do things for the current process.</li>
<li> Make the child process runnable by <code>sys_env_set_status</code>.</li>
</ol>
<p> The order of those things is rather important: we must register a page fault handler before the child is marked runnable. Otherwise if later we use a preemptive multiprocessing strategy, the child might start running on copy-on-write memory without a page fault handler.</p></li>
<li>sys_exofork()'s return value is a negative integer, which indicates failure.</li>
</ul>
<p> In all three cases, I chose not to <code>panic</code> on exceptional conditions, just delegate the return value to the caller of <code>fork</code> instead.</p></li>
</ol>
<p>Now we move on to the COW mapping-transferring function <code>duppage()</code>:</p>
<ul>
<li>For a virtual page that is originally mapped writable or copy-on-write, we map the page in both parent and child with COW permissions.
<ul>
<li>Why is it necessary to map in the parent those COW pages again?
<ul>
<li>no idea, not necessary according to my tests.</li>
</ul>
</li>
</ul>
</li>
<li>For a virtual page that is originally read-only, we map the page in the child read-only as well.</li>
<li>In case of any system call failure, <code>duppage()</code> will not panic but return the error code to the caller function.</li>
</ul>
<p>Next, the core of COW : page fault handler <code>pgfault()</code></p>
<ul>
<li><code>pgfault</code> first checks that the fault was caused by write to COW location. Otherwise it raise a <code>panic</code>. In a more realistic scene, <code>pgfault()</code> could delegate the 'otherwise' to another general page fault handler.</li>
<li>Then, <code>pgfault</code> allocate a new page at <code>PFTEMP</code>, map it to the faulting location (rounded down to nearest page boundary) with user-write permission, then undo the mapping at <code>PFTEMP</code>.</li>
</ul>
<p>Now our COW-fork mechanism is rather complete, moving on to testing <code>user/forktree</code> on single CPU (I modified the fork depth to 2):</p>
<pre><code>[00000000] new env 00001000
1000: I am ''
[00001000] new env 00001001
[00001000] new env 00001002
[00001000] exiting gracefully
[00001000] free env 00001000
1001: I am '0'
[00001001] new env 00002000
[00001001] new env 00001003
[00001001] exiting gracefully
[00001001] free env 00001001
2000: I am '00'
[00002000] exiting gracefully
[00002000] free env 00002000
1002: I am '1'
[00001002] new env 00003000
[00001002] new env 00002001
[00001002] exiting gracefully
[00001002] free env 00001002
3000: I am '10'
[00003000] exiting gracefully
[00003000] free env 00003000
2001: I am '11'
[00002001] exiting gracefully
[00002001] free env 00002001
1003: I am '01'
[00001003] exiting gracefully
[00001003] free env 00001003
No runnable environments in the system!
</code></pre>
<p>Part B of lab4 is complete.</p>
<hr />
<h2>Ex.13, 14 Clock Interrupts and Preemption</h2>
<p>IDT entries are already fully setup in the previous lab, using <code>generate_traps.py</code>. To allow user programs to accept interrupts, <code>FL_IF</code> flag in <code>flags</code> must be set in <code>env_alloc()</code>. Then when a clock interrupt <code>IRQ_OFFSET + IRQ_TIME</code> enters the trap dispatcher, we should first acknowledge it by <code>lapic_eoi()</code>, then call the scheduler <code>schedule_yield()</code> to enable preemption.</p>
<hr />
<h2>Ex.15 Implementing IPC</h2>
<p>Having all the previous work in help, IPC becomes pretty easy to implement. Our IPC mechanism supports the sender to send a 4-byte word to the receiver, optionally sharing a page of memory between. Four of the core functions:</p>
<ol>
<li>In kernel space (system calls):
<ol type="a">
<li><code>int sys_ipc_try_send(envid_t envid, uint32_t value, void *srcva, unsigned perm)</code> this function will try to locate a Env with <code>envid</code>, send the value to it only if the selected Env bas called <code>sys_ipc_recv</code> already to receive the value. If <code>srcva</code> and <code>perm</code> are meaningful, and that the receiver allowed shared mapping to be made, a page of memory from the sender at address <code>srcva</code> would be mapped to <code>dstva</code> of the receiver. This system call does not wait for the receiver to be ready, so the library wrapper must retry infinitely waiting for the receiver. This function must change the receiver to runnable state, and clear the <code>env_ipc_recving</code> flag after the message was sent.</li>
<li><code>int sys_ipc_recv(void *dstva)</code> A processing expecting a message from another process will call this function, to mark itself ready. This function does not return until the message is received.</li>
</ol>
</li>
<li>In user space (library calls):
<ol type="a">
<li><code>void ipc_send(envid_t to_env, uint32_t val, void *pg, int perm)</code> a library function that repeatedly calls <code>sys_ipc_try_send</code> to send a message to another process. This function would <code>panic</code> if the provided arguments are illegal.</li>
<li><code>int32_t ipc_recv(envid_t *from_env_store, void *pg, int *perm_store)</code> this wrapper calls <code>sys_ipc_recv</code>, upon return, it fills <code>from_env_store</code> and <code>perm_store</code> if necessary, then return the received 4-byte message to the caller.</li>
</ol>
</li>
</ol>
<hr />
<h2>Final testing:</h2>
<p>Now all exercises are complete, moving on to testing:</p>
<ol>
<li><p>My output for <code>user/badhandler</code> and <code>user/evilhandler</code> tests was different from the expected. After carefully reading this piece of comment in <code>kern/trap.c</code>:</p>
<pre><code> // Note that the grade script assumes you will first check for the page
// fault upcall and print the "user fault va" message below if there is
// none. The remaining three checks can be combined into a single test.
</code></pre>
<p>So in <code>page_fault_handler</code>, we must check both the existence and validity of user's page fault handler (using <code>user_mem_assert</code>) before other things, to make the grading script happy.</p></li>
<li><code>user/primes</code> not behaving correctly. Later I realised this was caused by a faulty <code>sys_ipc_try_send</code> that does not clear the receiver's <code>env_ipc_recving</code> flag after successfully transferring the message. When I fixed this, the maximum prime number <code>user/primes</code> calculated was <code>8147</code>, by the final process, afterwards <code>fork</code> failed because the OS ran out of space for <code>Env</code>.</li>
</ol>
<hr />
<p><strong>Now All exercises of Lab4 are done, all tests passed. (auto-grade does not work on OS X, tested manually)</strong></p>
</body>
</html>