Revisions.
[pintos-anon] / doc / vm.texi
1 @node Project 3--Virtual Memory, Project 4--File Systems, Project 2--User Programs, Top
2 @chapter Project 3: Virtual Memory
3
4 By now you should be familiar with the inner workings of Pintos.
5 You've already come a long way: your OS can properly handle multiple
6 threads of execution with proper synchronization, and can load
7 multiple user programs at once.  However, when loading user programs,
8 your OS is limited by how much main memory the simulated machine has.
9 In this assignment, you will remove that limitation.
10
11 You will be using the @file{vm} directory for this project.  The
12 @file{vm} directory contains only the @file{Makefile}s.  The only
13 change from @file{userprog} is that this new @file{Makefile} turns on
14 the setting @option{-DVM}.  All code you write will either be newly
15 generated files (e.g.@: if you choose to implement your paging code in
16 their own source files), or will be modifications to pre-existing code
17 (e.g.@: you will change the behavior of @file{process.c}
18 significantly).
19
20 There are only a couple of source files you will probably be
21 encountering for the first time:
22
23 @table @file
24 @item devices/disk.h
25 @itemx devices/disk.c
26 Provides access to the physical disk, abstracting away the rather
27 awful IDE interface.
28 @end table
29
30 You will be building this assignment on the last one.  It will benefit
31 you to get your project 2 in good working order before this assignment
32 so those bugs don't keep haunting you.
33
34 All the test programs from the previous project should also work with
35 this project.  You should also write programs to test the new features
36 introduced in this project.
37
38 Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
39 @file{constants.h} (@pxref{Conditional Compilation}).
40
41 @menu
42 * VM Design::                   
43 * Page Faults::                 
44 * Disk as Backing Store::       
45 * Memory Mapped Files::         
46 * Stack::                       
47 * Problem 3-1 Page Table Management::  
48 * Problem 3-2 Paging To and From Disk::  
49 * Problem 3-3 Memory Mapped Files::  
50 * Virtual Memory FAQ::          
51 @end menu
52
53 @node VM Design
54 @section A Word about Design
55
56 It is important for you to note that in addition to getting virtual
57 memory working, this assignment is also meant to be an open-ended
58 design problem.  We will expect you to come up with a design that
59 makes sense.  You will have the freedom to choose how to handle page
60 faults, how to organize the swap disk, how to implement paging, etc.
61 In each case, we will expect you to provide a defensible justification
62 in your design documentation as to why your choices are reasonable.
63 You should evaluate your design on all the available criteria: speed
64 of handling a page fault, space overhead in memory, minimizing the
65 number of page faults, simplicity, etc.
66
67 In keeping with this, you will find that we are going to say as little
68 as possible about how to do things.  Instead we will focus on what end
69 functionality we require your OS to support.
70
71 @node Page Faults
72 @section Page Faults
73
74 For the last assignment, whenever a context switch occurred, the new
75 process would install its own page table into the machine.  The page
76 table contained all the virtual-to-physical translations for the
77 process.  Whenever the processor needed to look up a translation, it
78 consulted the page table.  As long as the process only accessed
79 memory that it didn't own, all was well.  If the process accessed
80 memory it didn't own, it ``page faulted'' and @func{page_fault}
81 terminated the process.
82
83 When we implement virtual memory, the rules have to change.  A page
84 fault is no longer necessarily an error, since it might only indicate
85 that the page must be brought in from a disk file or from swap.  You
86 will have to implement a more sophisticated page fault handler to
87 handle these cases.
88
89 On the 80@var{x}86, the page table format is fixed by hardware.  We
90 have provided code for managing page tables for you to use in
91 @file{userprog/pagedir.c}.  The functions in there should provide an
92 abstract interface to all the page table functionality that you need
93 to complete the project.  However, you may still find it worthwhile to
94 understand a little about the hardware page table format, so we'll go
95 into a little of detail about that in this section.
96
97 The top-level paging data structure is a 4 kB page called the ``page
98 directory'' (PD) arranged as an array of 1,024 32-bit page directory
99 entries (PDEs), each of which represents 4 MB of virtual memory.  Each
100 PDE may point to the physical address of another 4 kB page called a
101 ``page table'' (PT) arranged in the same fashion as an array of 1,024
102 32-bit page table entries (PTEs), each of which translates a single 4
103 kB virtual page into physical memory.
104
105 Thus, translation of a virtual address into a physical address follows
106 the three-step process illustrated in the diagram
107 below:@footnote{Actually, virtual to physical translation on the
108 80@var{x}86 architecture happens via an intermediate ``linear
109 address,'' but Pintos (and most other 80@var{x}86 OSes) set up the CPU
110 so that linear and virtual addresses are one and the same, so that you
111 can effectively ignore this CPU feature.}
112
113 @enumerate 1
114 @item
115 The top 10 bits of the virtual address (bits 22:32) are used to index
116 into the page directory.  If the PDE is marked ``present,'' the
117 physical address of a page table is read from the PDE thus obtained.
118 If the PDE is marked ``not present'' then a page fault occurs.
119
120 @item
121 The next 10 bits of the virtual address (bits 12:22) are used to index
122 into the page table.  If the PTE is marked ``present,'' the physical
123 address of a data page is read from the PTE thus obtained.  If the PTE
124 is marked ``not present'' then a page fault occurs.
125
126
127 @item
128 The bottom 12 bits of the virtual address (bits 0:12) are added to the
129 data page's physical base address, producing the final physical
130 address.
131 @end enumerate
132
133 @example
134 @group
135 32                    22                     12                      0
136 +--------------------------------------------------------------------+
137 | Page Directory Index |   Page Table Index   |    Page Offset       |
138 +--------------------------------------------------------------------+
139              |                    |                     |
140      _______/             _______/                _____/
141     /                    /                       /
142    /    Page Directory  /      Page Table       /    Data Page
143   /     .____________. /     .____________.    /   .____________.
144   |1,023|____________| |1,023|____________|    |   |____________|
145   |1,022|____________| |1,022|____________|    |   |____________|
146   |1,021|____________| |1,021|____________|    \__\|____________|
147   |1,020|____________| |1,020|____________|       /|____________|
148   |     |            | |     |            |        |            |
149   |     |            | \____\|            |_       |            |
150   |     |      .     |      /|      .     | \      |      .     |
151   \____\|      .     |_      |      .     |  |     |      .     |
152        /|      .     | \     |      .     |  |     |      .     |
153         |      .     |  |    |      .     |  |     |      .     |
154         |            |  |    |            |  |     |            |
155         |____________|  |    |____________|  |     |____________|
156        4|____________|  |   4|____________|  |     |____________|
157        3|____________|  |   3|____________|  |     |____________|
158        2|____________|  |   2|____________|  |     |____________|
159        1|____________|  |   1|____________|  |     |____________|
160        0|____________|  \__\0|____________|  \____\|____________|
161                            /                      /
162 @end group
163 @end example
164
165 Header @file{threads/mmu.h} has useful functions for various
166 operations on virtual addresses.  You should look over the header
167 yourself, but its most important functions include these:
168
169 @table @code
170 @item pd_no(@var{va})
171 Returns the page directory index in virtual address @var{va}.
172
173 @item pt_no(@var{va})
174 Returns the page table index in virtual address @var{va}.
175
176 @item pg_ofs(@var{va})
177 Returns the page offset in virtual address @var{va}.
178
179 @item pg_round_down(@var{va})
180 Returns @var{va} rounded down to the nearest page boundary, that is,
181 @var{va} but with its page offset set to 0.
182
183 @item pg_round_up(@var{va})
184 Returns @var{va} rounded up to the nearest page boundary.
185 @end table
186
187 @node Disk as Backing Store
188 @section Disk as Backing Store
189
190 In VM systems, since memory is less plentiful than disk, you will
191 effectively use memory as a cache for disk.  Looking at it from
192 another angle, you will use disk as a backing store for memory.  This
193 provides the abstraction of an (almost) unlimited virtual memory size.
194 Part of your task in this project is to do this, with the additional
195 constraint that your performance should be close to that provided by
196 physical memory.  You will use the page tables' ``dirty'' bits to
197 denote whether pages need to be written back to disk when they're
198 evicted from main memory and the ``accessed'' bit for page replacement
199 algorithms.  Whenever the hardware writes memory, it sets the dirty
200 bit, and if it reads or writes to the page, it sets the accessed bit.
201
202 As with any caching system, performance depends on the policy used to
203 decide which things are kept in memory and which are only stored on
204 disk.  On a page fault, the kernel must decide which page to replace.
205 Ideally, it will throw out a page that will not be referenced for a
206 long time, keeping in memory those pages that are soon to be
207 referenced.  Another consideration is that if the replaced page has
208 been modified, the page must be first saved to disk before the needed
209 page can be brought in.  Many virtual memory systems avoid this extra
210 overhead by writing modified pages to disk in advance, so that later
211 page faults can be completed more quickly (but you do not have to
212 implement this optimization).
213
214 @node Memory Mapped Files
215 @section Memory Mapped Files
216
217 The traditional way to access the file system is via @code{read} and
218 @code{write} system calls, but that requires an extra level of copying
219 between the kernel and the user level.  A secondary interface is
220 simply to ``map'' the file into the virtual address space.  The
221 program can then use load and store instructions directly on the file
222 data.  (An alternative way of viewing the file system is as ``durable
223 memory.''  Files just store data structures.  If you access data
224 structures in memory using load and store instructions, why not access
225 data structures in files the same way?)
226
227 Memory mapped files are typically implemented using system calls.  One
228 system call maps the file to a particular part of the address space.
229 For example, one might conceptually map the file @file{foo}, which is
230 1000 bytes
231 long, starting at address 5000.  Assuming that nothing else is already
232 at virtual addresses 5000@dots{}6000, any memory accesses to these
233 locations will access the corresponding bytes of @file{foo}.
234
235 A consequence of memory mapped files is that address spaces are
236 sparsely populated with lots of segments, one for each memory mapped
237 file (plus one each for code, data, and stack).  You will implement
238 memory mapped files in problem 3-3.  You should
239 design your solutions to problems 3-1 and 3-2 to anticipate this.
240
241 @node Stack
242 @section Stack
243
244 In project 2, the stack was a single page at the top of the user
245 virtual address space.  The stack's location does not change in this
246 project, but your kernel should allocate additional pages to the stack
247 on demand.  That is, if the stack grows past its current bottom, the
248 system should allocate additional pages for the stack as necessary
249 (unless those pages are unavailable because they are in use by another
250 segment).
251
252 It is impossible to predict how large the stack will grow at compile
253 time, so we must allocate pages as necessary.  You should only allocate
254 additional pages if they ``appear'' to be stack accesses.  You must
255 devise a heuristic that attempts to distinguish stack accesses from
256 other accesses.@footnote{You might find it useful to know that the
257 80@var{x}86 instruction @code{pusha} pushes all 8 registers (32 bytes)
258 on the stack at once.}  Document and explain the heuristic in your
259 design documentation.
260
261 The first stack page need not be loaded lazily.  You can initialize it
262 with the command line at load time, with no need to wait for it to be
263 faulted in.  Even if you did wait, the very first instruction in the
264 user program is likely to be one that faults in the page.
265
266 Stack facts:
267
268 @itemize
269 @item
270 The user program's current stack pointer is in the @struct{intr_frame}'s
271 @code{esp} member.
272
273 @item
274 Only buggy user programs write to memory within the stack but below the
275 stack pointer.  This is because more advanced OSes may interrupt a
276 process at any time to deliver a ``signal'' and this uses the stack.
277
278 @item
279 The 80@var{x}86 @code{push} instruction may cause a page fault 4 bytes
280 below the stack pointer, because it checks access permissions before it
281 adjusts the stack pointer.  (Otherwise, the instruction would not be
282 restartable in a straightforward fashion.)
283
284 @item
285 Similarly, the 80@var{x}86 @code{pusha} instruction, which pushes all 32
286 bytes of the 8 general-purpose registers at once, may cause a page fault
287 32 bytes below the stack pointer.
288
289 @item
290 Most OSes impose some sort of limit on the stack size.  Sometimes it is
291 user-adjustable.
292 @end itemize
293
294 @node Problem 3-1 Page Table Management
295 @section Problem 3-1: Page Table Management
296
297 Implement page directory and page table management to support virtual
298 memory.  You will need data structures to accomplish the following
299 tasks:
300
301 @itemize @bullet
302 @item
303 Some way of translating in software from virtual page frames to
304 physical page frames.  Consider using a hash table (@pxref{Hash
305 Table}).
306
307 It is possible to do this translation without adding a new data
308 structure, by modifying the code in @file{userprog/pagedir.c}.  However,
309 if you do that you'll need to carefully study and understand section 3.7
310 in @bibref{IA32-v3}, and in practice it is probably easier to add a new
311 data structure.
312
313 @item
314 Some way of finding a page on disk if it is not in memory.  You won't
315 need this data structure until problem 3-2, but planning ahead is a
316 good idea.
317
318 You can generalize the virtual-to-physical page table, so that it allows
319 you to locate a page wherever it is in physical memory or on disk, or
320 you can make this a separate table.
321
322 @item
323 Some way of translating from physical page frames back to virtual page
324 frames, so that when you evict a physical page from its frame, you can
325 invalidate its translation(s).
326 @end itemize
327
328 The page fault handler, @func{page_fault} in
329 @file{threads/exception.c}, needs to do roughly the following:
330
331 @enumerate 1
332 @item
333 Locate the page backing the virtual
334 address that faulted.  It might be in the file system, in swap,
335 or it might be an invalid virtual address.
336 If you implement sharing, it might even
337 already be in physical memory and just not set up in the page table,
338
339 If the virtual address is invalid, that is, if there's nothing
340 assigned to go there, or if the virtual address is above
341 @code{PHYS_BASE}, meaning that it belongs to the kernel instead of the
342 user, then the process's memory access must be disallowed.  You should
343 terminate the process at this point, being sure to free all of its
344 resources.
345
346 @item
347 If the page is not in physical memory, fetch it by appropriate means.
348 If necessary to make room, first evict some other page from memory.
349 (When you do that you need to first remove references to the page from
350 any page table that refers to it.)
351
352 @item
353 Point the page table entry for the faulting virtual address to the
354 physical page.  You can use the functions in @file{userprog/pagedir.c}.
355 @end enumerate
356
357 You'll need to modify the ELF loader in @file{userprog/process.c} to
358 do page table management according to your new design.  As supplied,
359 it reads all the process's pages from disk and initializes the page
360 tables for them at the same time.  For testing purposes, you'll
361 probably want to leave the code that reads the pages from disk, but
362 use your new page table management code to construct the page tables
363 only as page faults occur for them.
364
365 You should use the @func{palloc_get_page} function to get the page
366 frames that you use for storing user virtual pages.  Be sure to pass
367 the @code{PAL_USER} flag to this function when you do so, because that
368 allocates pages from a ``user pool'' separate from the ``kernel pool''
369 that other calls to @func{palloc_get_page} make.
370
371 There are many possible ways to implement virtual memory.  The above
372 is simply an outline of our suggested implementation.
373
374 @node Problem 3-2 Paging To and From Disk
375 @section Problem 3-2: Paging To and From Disk
376
377 Implement paging to and from files and the swap disk.  You may use the
378 disk on interface @code{hd1:1} as the swap disk, using the disk
379 interface prototyped in @code{devices/disk.h}.
380
381 You will need routines to move a page from memory to disk and from
382 disk to memory, where ``disk'' is either a file or the swap disk.  If
383 you do everything correctly, your VM should still work when you
384 implement your own file system for the next assignment.
385
386 You will need a way to track pages which are used by a process but
387 which are not in physical memory, to fully handle page faults.  Pages
388 that you write to swap should not be constrained to be in sequential
389 order.  You will also need a way to track all of the physical memory
390 pages, to find an unused one when needed, or to evict a page
391 when memory is needed but no empty pages are available.  The data
392 structures that you designed for problem 3-1 should do most of the work for
393 you.
394
395 You will need a page replacement algorithm.  The hardware sets the
396 accessed and dirty bits when it accesses memory.  You can gain access
397 to this information using the functions prototyped in
398 @file{userprog/pagedir.h}.  You should be able to take advantage of
399 this information to implement some algorithm which attempts to achieve
400 LRU-type behavior.  We expect that your algorithm perform at least as
401 well as a reasonable implementation of the second-chance (clock)
402 algorithm.  You will need to show in your test cases the value of your
403 page replacement algorithm by demonstrating for some workload that it
404 pages less frequently using your algorithm than using some inferior
405 page replacement policy.  The canonical example of a poor page
406 replacement policy is random replacement.
407
408 You must write your code so that we can choose a page replacement policy
409 at compile time.  By default, the LRU-like algorithm must be in effect,
410 but we must be able to choose random replacement by inserting the line
411 @code{#define RANDOM_REPLACEMENT 1} in @file{constants.h}.
412 @xref{Conditional Compilation}, for details.
413
414 Since you will already be paging from disk, you should implement a
415 ``lazy'' loading scheme for new processes.  When a process is created,
416 it will not run immediately.  Therefore, it doesn't make sense to load
417 all its code, data, and stack into memory when the process is created,
418 since it might incur additional disk accesses to do so (if it gets
419 paged out before it runs).  When loading a new process, you should
420 leave most pages on disk, and bring them in as demanded when the
421 program begins running.  Your VM system should also use the executable
422 file itself as backing store for read-only segments, since these
423 segments won't change.
424
425 There are a few special cases.  Look at the loop in
426 @func{load_segment} in @file{userprog/process.c}.  Each time
427 around the loop, @code{read_bytes} represents the number of bytes to
428 read from the executable file and @code{zero_bytes} represents the number
429 of bytes to initialize to zero following the bytes read.  The two
430 always sum to @code{PGSIZE}.  The page handling depends on these
431 variables' values:
432
433 @itemize @bullet
434 @item
435 If @code{read_bytes} equals @code{PGSIZE}, the page should be demand
436 paged from disk on its first access.
437
438 @item 
439 If @code{zero_bytes} equals @code{PGSIZE}, the page does not need to
440 be read from disk at all because it is all zeroes.  You should handle
441 such pages by creating a new page consisting of all zeroes at the
442 first page fault.
443
444 @item
445 If neither @code{read_bytes} nor @code{zero_bytes} equals
446 @code{PGSIZE}, then part of the page is to be read from disk and the
447 remainder zeroed.  This is a special case.  You are allowed to handle
448 it by reading the partial page from disk at executable load time and
449 zeroing the rest of the page.  This is the only case in which we will
450 allow you to load a page in a non-``lazy'' fashion.  Many real OSes
451 such as Linux do not load partial pages lazily.
452 @end itemize
453
454 Incidentally, if you have trouble handling the third case above, you
455 can eliminate it temporarily by linking the test programs with a
456 special ``linker script.''  Read @file{tests/userprog/Makefile} for
457 details.  We will not test your submission with this special linker
458 script, so the code you turn in must properly handle all cases.
459
460 For extra credit, you may implement sharing: when multiple processes
461 are created that use the same executable file, share read-only pages
462 among those processes instead of creating separate copies of read-only
463 segments for each process.  If you carefully designed your data
464 structures in problem 3-1, sharing of read-only pages should not make this
465 part significantly harder.
466
467 @node Problem 3-3 Memory Mapped Files
468 @section Problem 3-3: Memory Mapped Files
469
470 Implement memory mapped files.
471
472 You will need to implement the following system calls:
473
474 @table @code
475 @item SYS_mmap
476 @itemx bool mmap (int @var{fd}, void *@var{addr}, unsigned @var{length})
477
478 Maps the file open as @var{fd} into the process's address space
479 starting at @var{addr} for @var{length} bytes.  Returns true if
480 successful, false on failure.  Failure cases include the following:
481
482 @itemize @bullet
483 @item
484 @var{addr} is not page-aligned.
485
486 @item
487 @var{length} is not positive.
488
489 @item
490 The range of pages mapped overlaps any existing set of mapped pages,
491 including the stack or pages mapped at executable load time.
492 @end itemize
493
494 @var{length} is treated as if it were rounded up to the nearest
495 multiple of the page size, that is, as if the first statement in the
496 system call's implementation were
497 @example
498 length = ROUND_UP (length, PGSIZE);
499 @end example
500 (The @code{ROUND_UP} macro is defined in @file{<round.h>}.)
501 The remainder of this description assumes that this has been done.
502
503 If @var{length} is less than @var{fd}'s length, you should only map
504 the first @var{length} bytes of the file.  If @var{length} is greater
505 than @var{fd}'s length, when the file's length is also rounded up to a
506 page multiple, the call should fail.  Ideally it would extend the
507 file, but our file system does not yet support growing files.
508
509 If @var{length} is greater than @var{fd}'s (unrounded) length, then some
510 bytes in the final mapped page ``stick out'' beyond the end of the
511 file.  Set these bytes to zero when the page is faulted in from
512 disk, and discard them when the page is written back to disk.
513
514 Your VM system should use the @code{mmap}'d file itself as
515 backing store for the mapped segment.  That is, to evict a page mapped by
516 @code{mmap} must be evicted, write it to the file it was mapped from.
517 (In fact, you may choose to implement executable mappings as a special
518 case of file mappings.)
519
520 @item SYS_munmap
521 @itemx bool munmap (void *addr, unsigned length)
522
523 Unmaps @var{length} bytes starting at @var{addr}.  Returns true on
524 success, false on failure.  Failure cases include the following:
525
526 @itemize @bullet
527 @item
528 @var{addr} is not page-aligned.
529
530 @item
531 @var{length} is not positive.
532
533 @item
534 One or more pages within the range to be unmapped were not mapped
535 using the @code{mmap} system call.
536 @end itemize
537
538 As with @code{mmap}, @var{length} is treated as if it were rounded up
539 to the nearest multiple of the page size.
540
541 It is valid to unmap only some of the pages that were mapped in a
542 previous system call.
543 @end table
544
545 All mappings are implicitly unmapped when a process exits, whether via
546 @code{exit} or by any other means.  When a file is unmapped, whether
547 implicitly or explicitly, all outstanding changes are written to the
548 file, and the pages are removed from the process's list of used
549 virtual pages.
550
551 @node Virtual Memory FAQ
552 @section FAQ
553
554 @enumerate 1
555 @item
556 @b{Do we need a working HW 2 to implement HW 3?}
557
558 Yes.
559
560 @item
561 @anchor{Hash Table}
562 @b{How do I use the hash table provided in @file{lib/kernel/hash.c}?}
563
564 First, you need to embed a @code{hash_elem} object as a member of the
565 object that the hash table will contain.  Each @code{hash_elem} allows
566 the object to a member of at most one hash table at a given time.  All
567 the hash table functions that deal with hash table items actually use
568 the address of a @code{hash_elem}.  You can convert a pointer to a
569 @code{hash_elem} member into a pointer to the structure in which
570 member is embedded using the @code{hash_entry} macro.
571
572 Second, you need to decide on a key type.  The key should be something
573 that is unique for each object, because a given hash table may not
574 contain two objects with equal keys.  Then you need to write two
575 functions.  The first is a @dfn{hash function} that converts a key
576 into an integer.  Some sample hash functions that you can use or just
577 examine are given in @file{lib/kernel/hash.c}.  The second function
578 needed is a @dfn{comparison function} that compares a pair and returns
579 true if the first is less than the second.  These two functions have
580 to be compatible with the prototypes for @code{hash_hash_func} and
581 @code{hash_less_func} in @file{lib/kernel/hash.h}.
582
583 Here's a quick example.  Suppose you want to put @struct{thread}s
584 in a hash table.  First, add a @code{hash_elem} to the thread
585 structure by adding a line to its definition:
586
587 @example
588 hash_elem h_elem;               /* Hash table element. */
589 @end example
590
591 We'll choose the @code{tid} member in @struct{thread} as the key,
592 and write a hash function and a comparison function:
593
594 @example
595 /* Returns a hash for E. */
596 unsigned
597 thread_hash (const hash_elem *e, void *aux UNUSED)
598 @{
599   struct thread *t = hash_entry (e, struct thread, h_elem);
600   return hash_int (t->tid);
601 @}
602
603 /* Returns true if A's tid is less than B's tid. */
604 bool
605 thread_less (const hash_elem *a_, const hash_elem *b_, 
606              void *aux UNUSED)
607 @{
608   struct thread *a = hash_entry (a_, struct thread, h_elem);
609   struct thread *b = hash_entry (b_, struct thread, h_elem);
610   return a->tid < b->tid;
611 @}
612 @end example
613
614 Then we can create a hash table like this:
615
616 @example
617 struct hash threads;
618
619 hash_init (&threads, thread_hash, thread_less, NULL);
620 @end example
621
622 Finally, if @code{@var{t}} is a pointer to a @struct{thread},
623 then we can insert it into the hash table with:
624
625 @example
626 hash_insert (&threads, &@var{t}->h_elem);
627 @end example
628
629 If you have any other questions about hash tables, the CS109
630 and CS161 textbooks have good chapters on them, or you can come
631 to any of the TA's office hours for further clarification.
632
633 @item
634 @b{What are the @var{aux} parameters to the hash table functions good
635 for?}
636
637 In simple cases you won't have any need for the @var{aux} parameters.
638 In these cases you can just pass a null pointer to @func{hash_init}
639 for @var{aux} and ignore the values passed to the hash function and
640 comparison functions.  (You'll get a compiler warning if you don't use
641 the @var{aux} parameter, but you can turn that off with the
642 @code{UNUSED} macro, as shown above, or you can just ignore it.)
643
644 @var{aux} is useful when you have some property of the data in the
645 hash table that's both constant and needed for hashing or comparisons,
646 but which is not stored in the data items themselves.  For example, if
647 the items in a hash table contain fixed-length strings, but the items
648 themselves don't indicate what that fixed length is, you could pass
649 the length as an @var{aux} parameter.
650
651 @item
652 @b{The current implementation of the hash table does not do something
653 that we need it to do. What gives?}
654
655 You are welcome to modify it.  It is not used by any of the code we
656 provided, so modifying it won't affect any code but yours.  Do
657 whatever it takes to make it work the way you want.
658
659 @item
660 @b{What controls the layout of user programs?}
661
662 The linker is responsible for the layout of a user program in
663 memory. The linker is directed by a ``linker script'' which tells it
664 the names and locations of the various program segments.  You can
665 learn more about linker scripts by reading the ``Scripts'' chapter in
666 the linker manual, accessible via @samp{info ld}.
667 @end enumerate
668
669 @menu
670 * Problem 3-1 and 3-2 FAQ::    
671 * Problem 3-3 Memory Mapped File FAQ::  
672 @end menu
673
674 @node Problem 3-1 and 3-2 FAQ
675 @subsection Problem 3-1 and 3-2 FAQ
676
677 @enumerate 1
678 @item
679 @b{Does the virtual memory system need to support growth of the data
680 segment?}
681
682 No.  The size of the data segment is determined by the linker.  We
683 still have no dynamic allocation in Pintos (although it is possible to
684 ``fake'' it at the user level by using memory-mapped files).  However,
685 implementing it would add little additional complexity to a
686 well-designed system.
687
688 @item
689 @b{Why do I need to pass @code{PAL_USER} to @func{palloc_get_page}
690 when I allocate physical page frames?}@anchor{Why PAL_USER?}
691
692 You can layer some other allocator on top of @func{palloc_get_page}
693 if you like, but it should be the underlying mechanism, directly or
694 indirectly, for two reasons.  First, running out of pages in the user
695 pool just causes user programs to page, but running out of pages in
696 the kernel pool will cause all kinds of problems, because many kernel
697 functions depend on being able to allocate memory.  Second, you can
698 use the @option{-ul} option to @command{pintos} to limit the size of
699 the user pool, which makes it easy to test your VM implementation with
700 various user memory sizes.
701 @end enumerate
702
703 @node Problem 3-3 Memory Mapped File FAQ
704 @subsection Problem 3-3: Memory Mapped File FAQ
705
706 @enumerate 1
707 @item
708 @b{How do we interact with memory-mapped files?}
709
710 Let's say you want to map a file called @file{foo} into your address
711 space at address @t{0x10000000}. You open the file, determine its
712 length, and then use @code{mmap}:
713
714 @example
715 #include <stdio.h>
716 #include <syscall.h>
717
718 int main (void)
719 @{
720     void *addr = (void *) 0x10000000;
721     int fd = open ("foo");
722     int length = filesize (fd);
723     if (mmap (fd, addr, length))
724         printf ("success!\n");
725 @}
726 @end example
727
728 Suppose @file{foo} is a text file and you want to print the first 64
729 bytes on the screen (assuming, of course, that the length of the file
730 is at least 64).  Without @code{mmap}, you'd need to allocate a
731 buffer, use @code{read} to get the data from the file into the buffer,
732 and finally use @code{write} to put the buffer out to the display. But
733 with the file mapped into your address space, you can directly address
734 it like so:
735
736 @example
737 write (addr, 64, STDOUT_FILENO);
738 @end example
739
740 Similarly, if you wanted to replace the first byte of the file,
741 all you need to do is:
742
743 @example
744 addr[0] = 'b';
745 @end example
746
747 When you're done using the memory-mapped file, you simply unmap
748 it:
749
750 @example
751 munmap (addr, length);
752 @end example
753
754 @item
755 @b{What if two processes memory-map the same file?}
756
757 There is no requirement in Pintos that the two processes see
758 consistent data.  Unix handles this by making the processes share the
759 same physical page, but the @code{mmap} system call also has an
760 argument allowing the client to specify whether the page is shared or
761 private (i.e.@: copy-on-write).
762
763 @item
764 @b{What happens if a user removes a @code{mmap}'d file?}
765
766 You should follow the Unix convention and the mapping should still be
767 valid.  @xref{Removing an Open File}, for more information.
768
769 @item
770 @b{What if a process writes to a page that is memory-mapped, but the
771 location written to in the memory-mapped page is past the end
772 of the memory-mapped file?}
773
774 Can't happen.  @code{mmap} checks that the mapped region is within the
775 file's length and Pintos provides no way to shorten a file.  (Until
776 project 4, there's no way to extend a file either.)  You can remove a
777 file, but the mapping remains valid (see the previous question).
778
779 @item
780 @b{Do we have to handle memory mapping @code{stdin} or @code{stdout}?}
781
782 No.  Memory mapping implies that a file has a length and that a user
783 can seek to any location in the file.  Since the console device has
784 neither of these properties, @code{mmap} should return false when the
785 user attempts to memory map a file descriptor for the console device.
786
787 @item
788 @b{What happens when a process exits with mapped files?}
789
790 When a process finishes, each of its mapped files is implicitly
791 unmapped.  When a process @code{mmap}s a file and then writes into the
792 area for the file it is making the assumption the changes will be
793 written to the file.
794
795 @item
796 @b{If a user closes a mapped file, should it be automatically
797 unmapped?}
798
799 No, once created the mapping is valid until @code{munmap} is called
800 or the process exits.
801 @end enumerate