-
Notifications
You must be signed in to change notification settings - Fork 9
/
Copy pathLab_ xv6 lazy page allocation.htm
220 lines (173 loc) · 8.13 KB
/
Lab_ xv6 lazy page allocation.htm
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
<!-- saved from url=(0052)https://pdos.csail.mit.edu/6.828/2019/labs/lazy.html -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<title>Lab: xv6 lazy page allocation</title>
<link rel="stylesheet" href="./Lab_ xv6 lazy page allocation_files/labs.css" type="text/css">
</head>
<body>
<h1>Lab: xv6 lazy page allocation</h1>
<p>
One of the many neat tricks an O/S can play with page table hardware
is lazy allocation of user-space heap memory. Xv6 applications ask the
kernel for heap memory using the sbrk() system call. In the kernel
we've given you, sbrk() allocates physical memory and maps it into the
process's virtual address space. However, there are programs that use
sbrk() to ask for large amounts of memory but never use most of it,
for example to implement large sparse arrays. To optimize for this
case, sophisticated kernels allocate user memory lazily. That is,
sbrk() doesn't allocate physical memory, but just remembers which
addresses are allocated. When the process first tries to use any given
page of memory, the CPU generates a page fault, which the kernel
handles by allocating physical memory, zeroing it, and mapping it.
You'll add this lazy allocation feature to xv6 in this lab.
</p><p>Before writing code, you should make sure you have read "Chapter 3:
Page Tables" from the <a href="https://pdos.csail.mit.edu/6.828/2019/xv6/book-riscv-rev0.pdf">xv6
book</a> and studied the corresponding code.
</p><pre> $ <kbd>git fetch</kbd>
$ <kbd>git checkout lazy</kbd>
</pre>
<h2>Print page table</h2>
<div class="required">
It's often worthwhile to invest time writing code that helps
debugging, so your first task is to implement a function that prints
the contents of a page table. Define the function in kernel/vm.c;
it has the following prototype: <tt>void vmprint(pagetable_t)</tt>.
This function will be handy for debugging and will make you familiar
with RISC-V page tables. Insert a call to <tt>vmprint</tt> in
exec.c to print the page table for the first user process; its
output should be as below.
</div>
<p>The output of <tt>vmprint</tt> for the first user-level process
should be as follows:
</p><pre>page table 0x0000000087f6e000
..0: pte 0x0000000021fda801 pa 0x0000000087f6a000
.. ..0: pte 0x0000000021fda401 pa 0x0000000087f69000
.. .. ..0: pte 0x0000000021fdac1f pa 0x0000000087f6b000
.. .. ..1: pte 0x0000000021fda00f pa 0x0000000087f68000
.. .. ..2: pte 0x0000000021fd9c1f pa 0x0000000087f67000
..255: pte 0x0000000021fdb401 pa 0x0000000087f6d000
.. ..511: pte 0x0000000021fdb001 pa 0x0000000087f6c000
.. .. ..510: pte 0x0000000021fdd807 pa 0x0000000087f76000
.. .. ..511: pte 0x000000002000200b pa 0x0000000080008000
</pre>
The first line prints the address of the argument of <tt>vmprint</tt>.
Each PTE line shows the PTE index in its page directory, the pte, the
physical address for the PTE. The output should also indicate the
level of the page directory: the top-level entries are preceeded by
"..", the next level down with another "..", and so on. You should
not print entries that are not mapped. In the above example, the
top-level page directory has mappings for entry 0 and 255. The next
level down for entry 0 has only index 0 mapped, and the bottom-level
for that index 0 has entries 0, 1, and 2 mapped.
Some hints:
<ul>
<li>Use the macros at the end of the file kernel/riscv.h.
</li><li>The function <tt>freewalk</tt> may be inspirational.
</li><li>Define the prototype for <tt>vmprint</tt> in kernel/defs.h so
that you can call it from exec.c.
</li></ul>
<h2>Eliminate allocation from sbrk()</h2>
<div class="required">
Your first task is to delete page allocation from the sbrk(n) system
call implementation, which is the function sys_sbrk() in sysproc.c. The
sbrk(n) system call grows the process's memory size by n bytes, and
then returns the start of the newly allocated region (i.e., the old
size). Your new sbrk(n) should just increment the process's size
(myproc()->sz) by n and return the old size. It should not allocate memory
-- so you should delete the call to growproc() (but you still need to
increase the process's size!).
</div>
<p>
Try to guess what the result of this modification will be: what will
break?
</p><p>
Make this modification, boot xv6, and type <tt>echo hi</tt> to the shell.
You should see something like this:
</p><pre>init: starting sh
$ echo hiusertrap(): unexpected scause 0x000000000000000f pid=3
sepc=0x0000000000001258 stval=0x0000000000004008
va=0x0000000000004000 pte=0x0000000000000000
panic: uvmunmap: not mapped
</pre>
The "usertrap(): ..." message is from the user trap handler in trap.c;
it has caught an exception that it does not know how to handle. Make
sure you understand why this page fault occurs. The "stval=0x0..04008"
indicates that the virtual address that caused the page fault is
0x4008.
<h2>Lazy allocation</h2>
<div class="required">
Modify the code in trap.c to respond to a page fault from user space
by mapping a newly-allocated page of physical memory at the faulting
address, and then returning back to user space to let the process
continue executing. You should add your code just before
the <tt>printf</tt> call that produced the "usertrap(): ..."
message. Your solution is acceptable if it passes usertests.
</div>
<p>A good way to start this lab is by fixing <tt>usertrap()</tt>
in <tt>trap.c</tt> so that you can run "echo hi" in the shell again.
Once that works, you will find some additional problems that have to
be solved to make usertests to work correctly. Here are some hints
to get going.
</p><ul>
<li>You can check whether a fault is a page fault by seeing if
r_scause() is 13 or 15 in usertrap().
</li><li>Look at the arguments to the printf() in usertrap() that reports
the page fault, in order to see how to find the virtual
address that caused the page fault.
</li><li>Steal code from uvmalloc() in vm.c, which is what sbrk()
calls (via growproc()). You'll need to call kalloc() and mappages().
</li><li>Use PGROUNDDOWN(va) to round the faulting virtual address
down to a page boundary.
</li><li>uvmunmap() will panic; modify it to not panic if some pages aren't mapped.
</li><li>If the kernel crashes, look up sepc in kernel/kernel.asm
</li><li>Use your print function from above to print the content of a page table.
</li><li>If you see the error "incomplete type proc", include "proc.h"
(and "spinlock.h").
</li></ul>
<p>
If all goes well, your lazy allocation code should result in <tt>echo
hi</tt> working. You should get at least one page fault (and thus lazy
allocation) in the shell, and perhaps two.
</p><h2>Usertests</h2>
<p>Now you have the basics working, fix your code so that all of usertests
passes:
</p><ul>
<li> Handle negative sbrk() arguments.
</li><li> Kill a process if it page-faults on a virtual memory address
higher than any allocated with sbrk().
</li><li> Handle fork() correctly.
</li><li> Handle the case in which a process passes a valid address
from sbrk()
to a system call such as read or write, but the memory for
that address has not yet been allocated.
</li><li> Handle out-of-memory correctly: if kalloc() fails in the
page fault handler, kill the current process.
</li><li> Handle faults on the invalid page below the stack.
</li></ul>
<p>Your solution is acceptable if your kernel passes lazytests and usertests:
</p><pre>$ <kbd> lazytests</kbd>
lazytests starting
running test lazy alloc
test lazy alloc: OK
running test lazy unmap...
usertrap(): ...
test lazy unmap: OK
running test out of memory
usertrap(): ...
test out of memory: OK
ALL TESTS PASSED
$ <kbd>usertests</kbd>
...
ALL TESTS PASSED
$
</pre>
<p>
</p><div class="warning">
<ul>
<li>Please run `make grade` to ensure that your code passes all of the tests</li>
<li>Commit any modified source code before running `make handin`</li>
<li>You can inspect the status of your submission and download the submitted code at <a href="https://6828.scripts.mit.edu/2019/handin.py/">https://6828.scripts.mit.edu/2019/handin.py/</a> </li>
</ul>
</div>
<p><b>This completes the lab.</b> Commit your changes and type make
handin in the lab directory to hand in your lab.
</p></body></html>