98a5db28ee581bb437472db99b3c14a324b05532
[pintos-anon] / vm.texi
1 @node Project 3--Virtual Memory
2 @chapter Project 3: Virtual Memory
3
4 By now you should have some familiarity with the inner workings of
5 Pintos.  Your
6 OS can properly handle multiple threads of execution with proper
7 synchronization, and can load multiple user programs at once.  However,
8 the number and size of programs that can run is limited by the machine's
9 main memory size.  In this assignment, you will remove that limitation.
10
11 You will build this assignment on top of the last one.  Test programs
12 from project 2 should also work with project 3.  You should take care to
13 fix any bugs in your project 2 submission before you start work on
14 project 3, because those bugs will most likely cause the same problems
15 in project 3.
16
17 You will continue to handle Pintos disks and file systems the same way
18 you did in the previous assignment (@pxref{Using the File System}).
19
20 @menu
21 * Project 3 Background::        
22 * Project 3 Suggested Order of Implementation::  
23 * Project 3 Requirements::      
24 * Project 3 FAQ::               
25 @end menu
26
27 @node Project 3 Background
28 @section Background
29
30 @menu
31 * Project 3 Source Files::      
32 * Memory Terminology::          
33 * Resource Management Overview::  
34 * Managing the Supplemental Page Table::  
35 * Managing the Frame Table::    
36 * Managing the Swap Table::     
37 * Managing Memory Mapped Files Back::  
38 @end menu
39
40 @node Project 3 Source Files
41 @subsection Source Files
42
43 You will work in the @file{vm} directory for this project.  The
44 @file{vm} directory contains only @file{Makefile}s.  The only
45 change from @file{userprog} is that this new @file{Makefile} turns on
46 the setting @option{-DVM}.  All code you write will be in new
47 files or in files introduced in earlier projects.
48
49 You will probably be encountering just a few files for the first time:
50
51 @table @file
52 @item devices/block.h
53 @itemx devices/block.c
54 Provides sector-based read and write access to block device.  You will
55 use this interface to access the swap partition as a block device.
56 @end table
57
58 @node Memory Terminology
59 @subsection Memory Terminology
60
61 Careful definitions are needed to keep discussion of virtual memory from
62 being confusing.  Thus, we begin by presenting some terminology for
63 memory and storage.  Some of these terms should be familiar from project
64 2 (@pxref{Virtual Memory Layout}), but much of it is new.
65
66 @menu
67 * Pages::                       
68 * Frames::                      
69 * Page Tables::                 
70 * Swap Slots::                  
71 @end menu
72
73 @node Pages
74 @subsubsection Pages
75
76 A @dfn{page}, sometimes called a @dfn{virtual page}, is a continuous
77 region of virtual memory 4,096 bytes (the @dfn{page size}) in length.  A
78 page must be @dfn{page-aligned}, that is, start on a virtual address
79 evenly divisible by the page size.  Thus, a 32-bit virtual address can
80 be divided into a 20-bit @dfn{page number} and a 12-bit @dfn{page
81 offset} (or just @dfn{offset}), like this:
82
83 @example
84 @group
85                31               12 11        0
86               +-------------------+-----------+
87               |    Page Number    |   Offset  |
88               +-------------------+-----------+
89                        Virtual Address
90 @end group
91 @end example
92
93 Each process has an independent set of @dfn{user (virtual) pages}, which
94 are those pages below virtual address @code{PHYS_BASE}, typically
95 @t{0xc0000000} (3 GB).  The set of @dfn{kernel (virtual) pages}, on the
96 other hand, is global, remaining the same regardless of what thread or
97 process is active.  The kernel may access both user and kernel pages,
98 but a user process may access only its own user pages.  @xref{Virtual
99 Memory Layout}, for more information.
100
101 Pintos provides several useful functions for working with virtual
102 addresses.  @xref{Virtual Addresses}, for details.
103
104 @node Frames
105 @subsubsection Frames
106
107 A @dfn{frame}, sometimes called a @dfn{physical frame} or a @dfn{page
108 frame}, is a continuous region of physical memory.  Like pages, frames
109 must be page-size and page-aligned.  Thus, a 32-bit physical address can
110 be divided into a 20-bit @dfn{frame number} and a 12-bit @dfn{frame
111 offset} (or just @dfn{offset}), like this:
112
113 @example
114 @group
115                31               12 11        0
116               +-------------------+-----------+
117               |    Frame Number   |   Offset  |
118               +-------------------+-----------+
119                        Physical Address
120 @end group
121 @end example
122
123 The 80@var{x}86 doesn't provide any way to directly access memory at a
124 physical address.  Pintos works around this by mapping kernel virtual
125 memory directly to physical memory: the first page of kernel virtual
126 memory is mapped to the first frame of physical memory, the second page
127 to the second frame, and so on.  Thus, frames can be accessed through
128 kernel virtual memory.  
129
130 Pintos provides functions for translating between physical addresses and
131 kernel virtual addresses.  @xref{Virtual Addresses}, for details.
132
133 @node Page Tables
134 @subsubsection Page Tables
135
136 In Pintos, a @dfn{page table} is a data structure that the CPU uses to
137 translate a virtual address to a physical address, that is, from a page
138 to a frame.  The page table format is dictated by the 80@var{x}86
139 architecture.  Pintos provides page table management code in
140 @file{pagedir.c} (@pxref{Page Table}).
141
142 The diagram below illustrates the relationship between pages and frames.
143 The virtual address, on the left, consists of a page number and an
144 offset.  The page table translates the page number into a frame number,
145 which is combined with the unmodified offset to obtain the physical
146 address, on the right.
147
148 @example
149 @group
150                          +----------+
151         .--------------->|Page Table|-----------.
152        /                 +----------+            |
153    0   |  12 11 0                            0   V  12 11 0
154   +---------+----+                          +---------+----+
155   |Page Nr  | Ofs|                          |Frame Nr | Ofs|
156   +---------+----+                          +---------+----+
157    Virt Addr   |                             Phys Addr   ^
158                 \_______________________________________/
159 @end group
160 @end example
161
162 @node Swap Slots
163 @subsubsection Swap Slots
164
165 A @dfn{swap slot} is a continuous, page-size region of disk space in the
166 swap partition.  Although hardware limitations dictating the placement of
167 slots are looser than for pages and frames, swap slots should be
168 page-aligned because there is no downside in doing so.
169
170 @node Resource Management Overview
171 @subsection Resource Management Overview
172
173 You will need to design the following data structures:
174
175 @table @asis
176 @item Supplemental page table
177
178 Enables page fault handling by supplementing the page table.
179 @xref{Managing the Supplemental Page Table}.
180
181 @item Frame table
182
183 Allows efficient implementation of eviction policy.
184 @xref{Managing the Frame Table}.
185
186 @item Swap table
187
188 Tracks usage of swap slots.
189 @xref{Managing the Swap Table}.
190
191 @item Table of file mappings
192
193 Processes may map files into their virtual memory space.  You need a
194 table to track which files are mapped into which pages.
195 @end table
196
197 You do not necessarily need to implement four completely distinct data
198 structures: it may be convenient to wholly or partially merge related
199 resources into a unified data structure.
200
201 For each data structure, you need to determine what information each
202 element should contain.  You also need to decide on the data structure's
203 scope, either local (per-process) or global (applying to the whole
204 system), and how many instances are required within its scope.
205
206 To simplify your design, you may store these data structures in
207 non-pageable memory.  That means that you can be sure that pointers
208 among them will remain valid.
209
210 Possible choices of data structures include arrays, lists, bitmaps, and
211 hash tables.  An array is often the simplest approach, but a sparsely
212 populated array wastes memory.  Lists are also simple, but traversing a
213 long list to find a particular position wastes time.  Both arrays and
214 lists can be resized, but lists more efficiently support insertion and
215 deletion in the middle.
216
217 Pintos includes a bitmap data structure in @file{lib/kernel/bitmap.c}
218 and @file{lib/kernel/bitmap.h}.  A bitmap is an array of bits, each of
219 which can be true or false.  Bitmaps are typically used to track usage
220 in a set of (identical) resources: if resource @var{n} is in use, then
221 bit @var{n} of the bitmap is true.  Pintos bitmaps are fixed in size,
222 although you could extend their implementation to support resizing.
223
224 Pintos also includes a hash table data structure (@pxref{Hash Table}).
225 Pintos hash tables efficiently support insertions and deletions over a
226 wide range of table sizes.
227
228 Although more complex data structures may yield performance or other
229 benefits, they may also needlessly complicate your implementation.
230 Thus, we do not recommend implementing any advanced data structure
231 (e.g.@: a balanced binary tree) as part of your design.
232
233 @node Managing the Supplemental Page Table
234 @subsection Managing the Supplemental Page Table
235
236 The @dfn{supplemental page table} supplements the page table with
237 additional data about each page.  It is needed because of the
238 limitations imposed by the page table's format.  Such a data structure
239 is often called a ``page table'' also; we add the word ``supplemental''
240 to reduce confusion.
241
242 The supplemental page table is used for at least two purposes.  Most
243 importantly, on a page fault, the kernel looks up the virtual page that
244 faulted in the supplemental page table to find out what data should be
245 there.  Second, the kernel consults the supplemental page table when a
246 process terminates, to decide what resources to free.
247
248 You may organize the supplemental page table as you wish.  There are at
249 least two basic approaches to its organization: in terms of segments or
250 in terms of pages.  Optionally, you may use the page table itself as an
251 index to track the members of the supplemental page table.  You will
252 have to modify the Pintos page table implementation in @file{pagedir.c}
253 to do so.  We recommend this approach for advanced students only.
254 @xref{Page Table Entry Format}, for more information.
255
256 The most important user of the supplemental page table is the page fault
257 handler.  In project 2, a page fault always indicated a bug in the
258 kernel or a user program.  In project 3, this is no longer true.  Now, a
259 page fault might only indicate that the page must be brought in from a
260 file or swap.  You will have to implement a more sophisticated page
261 fault handler to handle these cases.  Your page fault handler, which you
262 should implement by modifying @func{page_fault} in
263 @file{userprog/exception.c}, needs to do roughly the following:
264
265 @enumerate 1
266 @item
267 Locate the page that faulted in the supplemental page table.  If the
268 memory reference is valid, use the supplemental page table entry to
269 locate the data that goes in the page, which might be in the file
270 system, or in a swap slot, or it might simply be an all-zero page.  If
271 you implement sharing, the page's data might even already be in a page
272 frame, but not in the page table.
273
274 If the supplemental page table indicates that the user process should
275 not expect any data at the address it was trying to access, or if the
276 page lies within kernel virtual memory, or if the access is an attempt
277 to write to a read-only page, then the access is invalid.  Any invalid
278 access terminates the process and thereby frees all of its resources.
279
280 @item
281 Obtain a frame to store the page.  @xref{Managing the Frame Table}, for
282 details.
283
284 If you implement sharing, the data you need may already be in a frame,
285 in which case you must be able to locate that frame.
286
287 @item
288 Fetch the data into the frame, by reading it from the file system or
289 swap, zeroing it, etc.
290
291 If you implement sharing, the page you need may already be in a frame,
292 in which case no action is necessary in this step.
293
294 @item
295 Point the page table entry for the faulting virtual address to the
296 physical page.  You can use the functions in @file{userprog/pagedir.c}.
297 @end enumerate
298
299 @node Managing the Frame Table
300 @subsection Managing the Frame Table
301
302 The @dfn{frame table} contains one entry for each frame that contains a
303 user page.  Each entry in the frame table contains a pointer to the
304 page, if any, that currently occupies it, and other data of your choice.
305 The frame table allows Pintos to efficiently implement an eviction
306 policy, by choosing a page to evict when no frames are free.
307
308 The frames used for user pages should be obtained from the ``user
309 pool,'' by calling @code{palloc_get_page(PAL_USER)}.  You must use
310 @code{PAL_USER} to avoid allocating from the ``kernel pool,'' which
311 could cause some test cases to fail unexpectedly (@pxref{Why
312 PAL_USER?}).  If you modify @file{palloc.c} as part of your frame table
313 implementation, be sure to retain the distinction between the two pools.
314
315 The most important operation on the frame table is obtaining an unused
316 frame.  This is easy when a frame is free.  When none is free, a frame
317 must be made free by evicting some page from its frame.
318
319 If no frame can be evicted without allocating a swap slot, but swap is
320 full, panic the kernel.  Real OSes apply a wide range of policies to
321 recover from or prevent such situations, but these policies are beyond
322 the scope of this project.
323
324 The process of eviction comprises roughly the following steps:
325
326 @enumerate 1
327 @item
328 Choose a frame to evict, using your page replacement algorithm.  The
329 ``accessed'' and ``dirty'' bits in the page table, described below, will
330 come in handy.
331
332 @item
333 Remove references to the frame from any page table that refers to it.
334
335 Unless you have implemented sharing, only a single page should refer to
336 a frame at any given time.
337
338 @item
339 If necessary, write the page to the file system or to swap.
340 @end enumerate
341
342 The evicted frame may then be used to store a different page.
343
344 @menu
345 * Accessed and Dirty Bits::     
346 @end menu
347
348 @node Accessed and Dirty Bits
349 @subsubsection Accessed and Dirty Bits
350
351 80@var{x}86 hardware provides some assistance for implementing page
352 replacement algorithms, through a pair of bits in the page table entry
353 (PTE) for each page.  On any read or write to a page, the CPU sets the
354 @dfn{accessed bit} to 1 in the page's PTE, and on any write, the CPU
355 sets the @dfn{dirty bit} to 1.  The CPU never resets these bits to 0,
356 but the OS may do so.
357
358 You need to be aware of @dfn{aliases}, that is, two (or more) pages that
359 refer to the same frame.  When an aliased frame is accessed, the
360 accessed and dirty bits are updated in only one page table entry (the
361 one for the page used for access).  The accessed and dirty bits for the
362 other aliases are not updated.
363
364 In Pintos, every user virtual page is aliased to its kernel virtual
365 page.  You must manage these aliases somehow.  For example, your code
366 could check and update the accessed and dirty bits for both addresses.
367 Alternatively, the kernel could avoid the problem by only accessing user
368 data through the user virtual address.
369
370 Other aliases should only arise if you implement sharing for extra
371 credit (@pxref{VM Extra Credit}), or if there is a bug in your code.
372
373 @xref{Page Table Accessed and Dirty Bits}, for details of the functions
374 to work with accessed and dirty bits.
375
376 @node Managing the Swap Table
377 @subsection Managing the Swap Table
378
379 The swap table tracks in-use and free swap slots.  It should allow
380 picking an unused swap slot for evicting a page from its frame to the
381 swap partition.  It should allow freeing a swap slot when its page is read
382 back or the process whose page was swapped is terminated.
383
384 You may use the @code{BLOCK_SWAP} block device for swapping, obtaining
385 the @struct{block} that represents it by calling @func{block_get_role}.
386 From the
387 @file{vm/build} directory, use the command @code{pintos-mkdisk swap.dsk
388 --swap-size=@var{n}} to create an disk named @file{swap.dsk} that
389 contains a @var{n}-MB swap partition.
390 Afterward, @file{swap.dsk} will automatically be attached as an extra disk
391 when you run @command{pintos}.  Alternatively, you can tell
392 @command{pintos} to use a temporary @var{n}-MB swap disk for a single
393 run with @option{--swap-size=@var{n}}.
394
395 Swap slots should be allocated lazily, that is, only when they are
396 actually required by eviction.  Reading data pages from the executable
397 and writing them to swap immediately at process startup is not lazy.
398 Swap slots should not be reserved to store particular pages.
399
400 Free a swap slot when its contents are read back into a frame.
401
402 @node Managing Memory Mapped Files Back
403 @subsection Managing Memory Mapped Files
404
405 The file system is most commonly accessed with @code{read} and
406 @code{write} system calls.  A secondary interface is to ``map'' the file
407 into virtual pages, using the @code{mmap} system call.  The program can
408 then use memory instructions directly on the file data.
409
410 Suppose file @file{foo} is @t{0x1000} bytes (4 kB, or one page) long.
411 If @file{foo} is mapped into memory starting at address @t{0x5000}, then
412 any memory accesses to locations @t{0x5000}@dots{}@t{0x5fff} will access
413 the corresponding bytes of @file{foo}.
414
415 Here's a program that uses @code{mmap} to print a file to the console.
416 It opens the file specified on the command line, maps it at virtual
417 address @t{0x10000000}, writes the mapped data to the console (fd 1),
418 and unmaps the file.
419
420 @example
421 #include <stdio.h>
422 #include <syscall.h>
423 int main (int argc UNUSED, char *argv[]) 
424 @{
425   void *data = (void *) 0x10000000;     /* @r{Address at which to map.} */
426
427   int fd = open (argv[1]);              /* @r{Open file.} */
428   mapid_t map = mmap (fd, data);        /* @r{Map file.} */
429   write (1, data, filesize (fd));       /* @r{Write file to console.} */
430   munmap (map);                         /* @r{Unmap file (optional).} */
431   return 0;
432 @}
433 @end example
434
435 A similar program with full error handling is included as @file{mcat.c}
436 in the @file{examples} directory, which also contains @file{mcp.c} as a
437 second example of @code{mmap}.
438
439 Your submission must be able to track what memory is used by memory
440 mapped files.  This is necessary to properly handle page faults in the
441 mapped regions and to ensure that mapped files do not overlap any other
442 segments within the process.
443
444 @node Project 3 Suggested Order of Implementation
445 @section Suggested Order of Implementation
446
447 We suggest the following initial order of implementation:
448
449 @enumerate 1
450 @item
451 Frame table (@pxref{Managing the Frame Table}).  Change @file{process.c}
452 to use your frame table allocator.
453
454 Do not implement swapping yet.  If you run out of frames, fail the
455 allocator or panic the kernel.
456
457 After this step, your kernel should still pass all the project 2 test
458 cases.
459
460 @item
461 Supplemental page table and page fault handler (@pxref{Managing the
462 Supplemental Page Table}).  Change @file{process.c} to record the
463 necessary information in the supplemental page table when loading an
464 executable and setting up its stack.  Implement loading of code and data
465 segments in the page fault handler.  For now, consider only valid
466 accesses.
467
468 After this step, your kernel should pass all of the project 2
469 functionality test cases, but only some of the robustness tests.
470 @end enumerate
471
472 From here, you can implement stack growth, mapped files, and page
473 reclamation on process exit in parallel.
474
475 The next step is to implement eviction (@pxref{Managing the Frame
476 Table}).  Initially you could choose the page to evict randomly.  At
477 this point, you need to consider how to manage accessed and dirty bits
478 and aliasing of user and kernel pages.  Synchronization is also a
479 concern: how do you deal with it if process A faults on a page whose
480 frame process B is in the process of evicting?  Finally, implement a
481 eviction strategy such as the clock algorithm.
482
483 @node Project 3 Requirements
484 @section Requirements
485
486 This assignment is an open-ended design problem.  We are going to say as
487 little as possible about how to do things.  Instead we will focus on
488 what functionality we require your OS to support.  We will expect
489 you to come up with a design that makes sense.  You will have the
490 freedom to choose how to handle page faults, how to organize the swap
491 partition, how to implement paging, etc.
492
493 @menu
494 * Project 3 Design Document::   
495 * Paging::                      
496 * Stack Growth::                
497 * Memory Mapped Files::         
498 @end menu
499
500 @node Project 3 Design Document
501 @subsection Design Document
502
503 Before you turn in your project, you must copy @uref{vm.tmpl, , the
504 project 3 design document template} into your source tree under the name
505 @file{pintos/src/vm/DESIGNDOC} and fill it in.  We recommend that you
506 read the design document template before you start working on the
507 project.  @xref{Project Documentation}, for a sample design document
508 that goes along with a fictitious project.
509
510 @node Paging
511 @subsection Paging
512
513 Implement paging for segments loaded from executables.  All of these
514 pages should be loaded lazily, that is, only as the kernel intercepts
515 page faults for them.  Upon eviction, pages modified since load (e.g.@:
516 as indicated by the ``dirty bit'') should be written to swap.
517 Unmodified pages, including read-only pages, should never be written to
518 swap because they can always be read back from the executable.
519
520 Implement a global page replacement algorithm that approximates LRU.
521 Your algorithm should perform at least as well as the simple variant
522 of the ``second chance'' or ``clock'' algorithm.
523
524 Your design should allow for parallelism.  If one page fault requires
525 I/O, in the meantime processes that do not fault should continue
526 executing and other page faults that do not require I/O should be able
527 to complete.  This will require some synchronization effort.
528
529 You'll need to modify the core of the program loader, which is the loop
530 in @func{load_segment} in @file{userprog/process.c}.  Each time around
531 the loop, @code{page_read_bytes} receives the number of bytes to read
532 from the executable file and @code{page_zero_bytes} receives the number
533 of bytes to initialize to zero following the bytes read.  The two always
534 sum to @code{PGSIZE} (4,096).  The handling of a page depends on these
535 variables' values:
536
537 @itemize @bullet
538 @item
539 If @code{page_read_bytes} equals @code{PGSIZE}, the page should be demand
540 paged from the underlying file on its first access.
541
542 @item
543 If @code{page_zero_bytes} equals @code{PGSIZE}, the page does not need to
544 be read from disk at all because it is all zeroes.  You should handle
545 such pages by creating a new page consisting of all zeroes at the
546 first page fault.
547
548 @item
549 Otherwise, neither @code{page_read_bytes} nor @code{page_zero_bytes}
550 equals @code{PGSIZE}.  In this case, an initial part of the page is to
551 be read from the underlying file and the remainder zeroed.
552 @end itemize
553
554 @node Stack Growth
555 @subsection Stack Growth
556
557 Implement stack growth.  In project 2, the stack was a single page at
558 the top of the user virtual address space, and programs were limited to
559 that much stack.  Now, if the stack grows past its current size,
560 allocate additional pages as necessary.
561
562 Allocate additional pages only if they ``appear'' to be stack accesses.
563 Devise a heuristic that attempts to distinguish stack accesses from
564 other accesses.
565
566 User programs are buggy if they write to the stack below the stack
567 pointer, because typical real OSes may interrupt a process at any time
568 to deliver a ``signal,'' which pushes data on the stack.@footnote{This rule is
569 common but not universal.  One modern exception is the
570 @uref{http://www.x86-64.org/documentation/abi.pdf, @var{x}86-64 System V
571 ABI}, which designates 128 bytes below the stack pointer as a ``red
572 zone'' that may not be modified by signal or interrupt handlers.}
573 However, the 80@var{x}86 @code{PUSH} instruction checks access
574 permissions before it adjusts the stack pointer, so it may cause a page
575 fault 4 bytes below the stack pointer.  (Otherwise, @code{PUSH} would
576 not be restartable in a straightforward fashion.)  Similarly, the
577 @code{PUSHA} instruction pushes 32 bytes at once, so it can fault 32
578 bytes below the stack pointer.
579
580 You will need to be able to obtain the current value of the user
581 program's stack pointer.  Within a system call or a page fault generated
582 by a user program, you can retrieve it from the @code{esp} member of the
583 @struct{intr_frame} passed to @func{syscall_handler} or
584 @func{page_fault}, respectively.  If you verify user pointers before
585 accessing them (@pxref{Accessing User Memory}), these are the only cases
586 you need to handle.  On the other hand, if you depend on page faults to
587 detect invalid memory access, you will need to handle another case,
588 where a page fault occurs in the kernel.  Since the processor only 
589 saves the stack pointer when an exception causes a switch from user
590 to kernel mode, reading @code{esp} out of the @struct{intr_frame} 
591 passed to @func{page_fault} would yield an undefined value, not the 
592 user stack pointer.  You will need to arrange another way, such as 
593 saving @code{esp} into @struct{thread} on the initial transition 
594 from user to kernel mode.
595
596 You should impose some absolute limit on stack size, as do most OSes.
597 Some OSes make the limit user-adjustable, e.g.@: with the
598 @command{ulimit} command on many Unix systems.  On many GNU/Linux systems,
599 the default limit is 8 MB.
600
601 The first stack page need not be allocated lazily.  You can allocate
602 and initialize it with the command line arguments at load time, with 
603 no need to wait for it to be faulted in.
604
605 All stack pages should be candidates for eviction.  An evicted stack
606 page should be written to swap.
607
608 @node Memory Mapped Files
609 @subsection Memory Mapped Files
610
611 Implement memory mapped files, including the following system calls.
612
613 @deftypefn {System Call} mapid_t mmap (int @var{fd}, void *@var{addr})
614 Maps the file open as @var{fd} into the process's virtual address
615 space.  The entire file is mapped into consecutive virtual pages
616 starting at @var{addr}.
617
618 Your VM system must lazily load pages in @code{mmap} regions and use the
619 @code{mmap}ed file itself as backing store for the mapping.  That is,
620 evicting a page mapped by @code{mmap} writes it back to the file it was
621 mapped from.
622
623 If the file's length is not a multiple of @code{PGSIZE}, then some
624 bytes in the final mapped page ``stick out'' beyond the end of the
625 file.  Set these bytes to zero when the page is faulted in from the
626 file system,
627 and discard them when the page is written back to disk.
628
629 If successful, this function returns a ``mapping ID'' that
630 uniquely identifies the mapping within the process.  On failure,
631 it must return -1, which otherwise should not be a valid mapping id,
632 and the process's mappings must be unchanged.
633
634 A call to @code{mmap} may fail if the file open as @var{fd} has a
635 length of zero bytes.  It must fail if @var{addr} is not page-aligned
636 or if the range of pages mapped overlaps any existing set of mapped
637 pages, including the stack or pages mapped at executable load time.
638 It must also fail if @var{addr} is 0, because some Pintos code assumes
639 virtual page 0 is not mapped.  Finally, file descriptors 0 and 1,
640 representing console input and output, are not mappable.
641 @end deftypefn
642
643 @deftypefn {System Call} void munmap (mapid_t @var{mapping})
644 Unmaps the mapping designated by @var{mapping}, which must be a
645 mapping ID returned by a previous call to @code{mmap} by the same
646 process that has not yet been unmapped.
647 @end deftypefn
648
649 All mappings are implicitly unmapped when a process exits, whether via
650 @code{exit} or by any other means.  When a mapping is unmapped, whether
651 implicitly or explicitly, all pages written to by the process are
652 written back to the file, and pages not written must not be.  The pages
653 are then removed from the process's list of virtual pages.
654
655 Closing or removing a file does not unmap any of its mappings.  Once
656 created, a mapping is valid until @code{munmap} is called or the process
657 exits, following the Unix convention.  @xref{Removing an Open File}, for
658 more information.  You should use the @code{file_reopen} function to
659 obtain a separate and independent reference to the file for each of
660 its mappings.
661
662 If two or more processes map the same file, there is no requirement that
663 they see consistent data.  Unix handles this by making the two mappings
664 share the same physical page, but the @code{mmap} system call also has
665 an argument allowing the client to specify whether the page is shared or
666 private (i.e.@: copy-on-write).
667
668 @subsection Accessing User Memory
669 You will need to adapt your code to access user memory (@pxref{Accessing
670 User Memory}) while handling a system call.  Just as user processes may
671 access pages whose content is currently in a file or in swap space, so
672 can they pass addresses that refer to such non-resident pages to system
673 calls.  Moreover, unless your kernel takes measures to prevent this,
674 a page may be evicted from its frame even while it is being accessed
675 by kernel code.  If kernel code accesses such non-resident user pages,
676 a page fault will result.
677
678 While accessing user memory, your kernel must either be prepared to handle
679 such page faults, or it must prevent them from occurring.  The kernel 
680 must prevent such page faults while it is holding resources it would 
681 need to acquire to handle these faults.  In Pintos, such resources include
682 locks acquired by the device driver(s) that control the device(s) containing 
683 the file system and swap space.  As a concrete example, you must not 
684 allow page faults to occur while a device driver accesses a user buffer
685 passed to @code{file_read}, because you would not be able to invoke
686 the driver while handling such faults.
687
688 Preventing such page faults requires cooperation between the code within
689 which the access occurs and your page eviction code.  For instance,
690 you could extend your frame table to record when a page contained in
691 a frame must not be evicted.  (This is also referred to as ``pinning''
692 or ``locking'' the page in its frame.)  Pinning restricts your page
693 replacement algorithm's choices when looking for pages to evict, so be
694 sure to pin pages no longer than necessary, and avoid pinning pages when
695 it is not necessary.
696
697 @node Project 3 FAQ
698 @section FAQ
699
700 @table @b
701 @item How much code will I need to write?
702
703 Here's a summary of our reference solution, produced by the
704 @command{diffstat} program.  The final row gives total lines inserted
705 and deleted; a changed line counts as both an insertion and a deletion.
706
707 This summary is relative to the Pintos base code, but the reference
708 solution for project 3 starts from the reference solution to project 2.
709 @xref{Project 2 FAQ}, for the summary of project 2.
710
711 The reference solution represents just one possible solution.  Many
712 other solutions are also possible and many of those differ greatly from
713 the reference solution.  Some excellent solutions may not modify all the
714 files modified by the reference solution, and some may modify files not
715 modified by the reference solution.
716
717 @verbatim
718  Makefile.build       |    4
719  devices/timer.c      |   42 ++
720  threads/init.c       |    5
721  threads/interrupt.c  |    2
722  threads/thread.c     |   31 +
723  threads/thread.h     |   37 +-
724  userprog/exception.c |   12
725  userprog/pagedir.c   |   10
726  userprog/process.c   |  319 +++++++++++++-----
727  userprog/syscall.c   |  545 ++++++++++++++++++++++++++++++-
728  userprog/syscall.h   |    1
729  vm/frame.c           |  162 +++++++++
730  vm/frame.h           |   23 +
731  vm/page.c            |  297 ++++++++++++++++
732  vm/page.h            |   50 ++
733  vm/swap.c            |   85 ++++
734  vm/swap.h            |   11
735  17 files changed, 1532 insertions(+), 104 deletions(-)
736 @end verbatim
737
738 @item Do we need a working Project 2 to implement Project 3?
739
740 Yes.
741
742 @item What extra credit is available?
743 @anchor{VM Extra Credit}
744
745 You may implement sharing: when multiple processes are created that use
746 the same executable file, share read-only pages among those processes
747 instead of creating separate copies of read-only segments for each
748 process.  If you carefully designed your data structures,
749 sharing of read-only pages should not make this part significantly
750 harder.
751
752 @item How do we resume a process after we have handled a page fault?
753
754 Returning from @func{page_fault} resumes the current user process
755 (@pxref{Internal Interrupt Handling}).
756 It will then retry the instruction to which the instruction pointer points.
757
758 @item Why do user processes sometimes fault above the stack pointer?
759
760 You might notice that, in the stack growth tests, the user program faults
761 on an address that is above the user program's current stack pointer,
762 even though the @code{PUSH} and @code{PUSHA} instructions would cause
763 faults 4 and 32 bytes below the current stack pointer.
764
765 This is not unusual.  The @code{PUSH} and @code{PUSHA} instructions are
766 not the only instructions that can trigger user stack growth.
767 For instance, a user program may allocate stack space by decrementing the 
768 stack pointer using a @code{SUB $n, %esp} instruction, and then use a 
769 @code{MOV ..., m(%esp)} instruction to write to a stack location within
770 the allocated space that is @var{m} bytes above the current stack pointer.  
771 Such accesses are perfectly valid, and your kernel must grow the 
772 user program's stack to allow those accesses to succeed.
773
774 @item Does the virtual memory system need to support data segment growth?
775
776 No.  The size of the data segment is determined by the linker.  We still
777 have no dynamic allocation in Pintos (although it is possible to
778 ``fake'' it at the user level by using memory-mapped files).  Supporting
779 data segment growth should add little additional complexity to a
780 well-designed system.
781
782 @item Why should I use @code{PAL_USER} for allocating page frames?
783 @anchor{Why PAL_USER?}
784
785 Passing @code{PAL_USER} to @func{palloc_get_page} causes it to allocate
786 memory from the user pool, instead of the main kernel pool.  Running out
787 of pages in the user pool just causes user programs to page, but running
788 out of pages in the kernel pool will cause many failures because so many
789 kernel functions need to obtain memory.
790 You can layer some other allocator on top of @func{palloc_get_page} if
791 you like, but it should be the underlying mechanism.
792
793 Also, you can use the @option{-ul} kernel command-line option to limit
794 the size of the user pool, which makes it easy to test your VM
795 implementation with various user memory sizes.
796 @end table