your OS is limited by how much main memory the simulated machine has.
In this assignment, you will remove that limitation.
-You will be using the @file{vm} directory for this project. There is
-no new code to get acquainted with for this assignment. The @file{vm}
-directory contains only the @file{Makefile}s. The only change from
-@file{userprog} is that this new @file{Makefile} turns on the setting
-@option{-DVM}. All code you write will either be newly generated
-files (e.g.@: if you choose to implement your paging code in their own
-source files), or will be modifications to pre-existing code (e.g.@:
-you will change the behavior of @file{process.c} significantly).
+You will be using the @file{vm} directory for this project. The
+@file{vm} directory contains only the @file{Makefile}s. The only
+change from @file{userprog} is that this new @file{Makefile} turns on
+the setting @option{-DVM}. All code you write will either be newly
+generated files (e.g.@: if you choose to implement your paging code in
+their own source files), or will be modifications to pre-existing code
+(e.g.@: you will change the behavior of @file{process.c}
+significantly).
+
+There are only a couple of source files you will probably be
+encountering for the first time:
+
+@table @file
+@item devices/disk.h
+@itemx devices/disk.c
+Provides access to the physical disk, abstracting away the rather
+awful IDE interface.
+@end table
You will be building this assignment on the last one. It will benefit
you to get your project 2 in good working order before this assignment
this project. You should also write programs to test the new features
introduced in this project.
-Your submission should define @code{THREAD_JOIN_IMPLEMENTED} in
-@file{constants.h} (@pxref{Conditional Compilation}).
+You will continue to handle Pintos disks and file systems the same way
+you did in the previous assignment (@pxref{Using the File System}).
@menu
* VM Design::
table contained all the virtual-to-physical translations for the
process. Whenever the processor needed to look up a translation, it
consulted the page table. As long as the process only accessed
-memory that it didn't own, all was well. If the process accessed
-memory it didn't own, it ``page faulted'' and @code{page_fault()}
+memory that it owned, all was well. If the process accessed
+memory it didn't own, it ``page faulted'' and @func{page_fault}
terminated the process.
When we implement virtual memory, the rules have to change. A page
will have to implement a more sophisticated page fault handler to
handle these cases.
-On the 80@var{x}86, the page table format is fixed by hardware. The
-top-level data structure is a 4 kB page called the ``page directory''
-(PD) arranged as an array of 1,024 32-bit page directory entries
-(PDEs), each of which represents 4 MB of virtual memory. Each PDE may
-point to the physical address of another 4 kB page called a ``page
-table'' (PT) arranged in the same fashion as an array of 1,024 32-bit
-page table entries (PTEs), each of which translates a single 4 kB
-virtual page into physical memory.
+On the 80@var{x}86, the page table format is fixed by hardware. We
+have provided code for managing page tables for you to use in
+@file{userprog/pagedir.c}. The functions in there should provide an
+abstract interface to all the page table functionality that you need
+to complete the project. However, you may still find it worthwhile to
+understand a little about the hardware page table format, so we'll go
+into a little of detail about that in this section.
+
+The top-level paging data structure is a 4 kB page called the ``page
+directory'' (PD) arranged as an array of 1,024 32-bit page directory
+entries (PDEs), each of which represents 4 MB of virtual memory. Each
+PDE may point to the physical address of another 4 kB page called a
+``page table'' (PT) arranged in the same fashion as an array of 1,024
+32-bit page table entries (PTEs), each of which translates a single 4
+kB virtual page into physical memory.
Thus, translation of a virtual address into a physical address follows
the three-step process illustrated in the diagram
@enumerate 1
@item
-The top 10 bits of the virtual address (bits 22:31) are used to index
+The top 10 bits of the virtual address (bits 22:32) are used to index
into the page directory. If the PDE is marked ``present,'' the
physical address of a page table is read from the PDE thus obtained.
If the PDE is marked ``not present'' then a page fault occurs.
@item
-The next 10 bits of the virtual address (bits 12:21) are used to index
+The next 10 bits of the virtual address (bits 12:22) are used to index
into the page table. If the PTE is marked ``present,'' the physical
address of a data page is read from the PTE thus obtained. If the PTE
is marked ``not present'' then a page fault occurs.
@item
-The bottom 12 bits of the virtual address (bits 0:11) are added to the
+The bottom 12 bits of the virtual address (bits 0:12) are added to the
data page's physical base address, producing the final physical
address.
@end enumerate
@example
+@group
32 22 12 0
+--------------------------------------------------------------------+
| Page Directory Index | Page Table Index | Page Offset |
1|____________| | 1|____________| | |____________|
0|____________| \__\0|____________| \____\|____________|
/ /
+@end group
@end example
Header @file{threads/mmu.h} has useful functions for various
been modified, the page must be first saved to disk before the needed
page can be brought in. Many virtual memory systems avoid this extra
overhead by writing modified pages to disk in advance, so that later
-page faults can be completed more quickly.
+page faults can be completed more quickly (but you do not have to
+implement this optimization).
@node Memory Mapped Files
@section Memory Mapped Files
Memory mapped files are typically implemented using system calls. One
system call maps the file to a particular part of the address space.
-For example, one might map the file @file{foo}, which is 1000 bytes
+For example, one might conceptually map the file @file{foo}, which is
+1000 bytes
long, starting at address 5000. Assuming that nothing else is already
at virtual addresses 5000@dots{}6000, any memory accesses to these
locations will access the corresponding bytes of @file{foo}.
A consequence of memory mapped files is that address spaces are
sparsely populated with lots of segments, one for each memory mapped
file (plus one each for code, data, and stack). You will implement
-memory mapped files for problem 3 of this assignment, but you should
-design your solutions to problems 1 and 2 to account for this.
+memory mapped files in problem 3-3. You should
+design your solutions to problems 3-1 and 3-2 to anticipate this.
@node Stack
@section Stack
virtual address space. The stack's location does not change in this
project, but your kernel should allocate additional pages to the stack
on demand. That is, if the stack grows past its current bottom, the
-system should allocate additional pages for the stack as necessary,
-unless those pages are unavailable because they are in use by another
-segment, in which case some sort of fault should occur.
+system should allocate additional pages for the stack as necessary
+(unless those pages are unavailable because they are in use by another
+segment).
+
+It is impossible to predict how large the stack will grow at compile
+time, so we must allocate pages as necessary. You should only allocate
+additional pages if they ``appear'' to be stack accesses. You must
+devise a heuristic that attempts to distinguish stack accesses from
+other accesses. Document and explain the heuristic in your
+design documentation.
+
+The first stack page need not be loaded lazily. You can initialize it
+with the command line at load time, with no need to wait for it to be
+faulted in. Even if you did wait, the very first instruction in the
+user program is likely to be one that faults in the page.
+
+Stack facts:
+
+@itemize
+@item
+The user program's current stack pointer is in the @struct{intr_frame}'s
+@code{esp} member.
+
+@item
+Only buggy 80@var{x}86 user programs write to memory within the
+stack but below the stack pointer. This is because more advanced OSes
+may interrupt a process at any time to deliver a ``signal'' and this
+uses the stack.@footnote{This rule is common but not universal. One
+modern exception is the
+@uref{http://www.x86-64.org/documentation/abi.pdf, @var{x}86-64 System
+V ABI}, which designates 128 bytes below the stack pointer as a ``red
+zone'' that may not be modified by signal or interrupt handlers.}
+
+@item
+The 80@var{x}86 @code{push} instruction may cause a page fault 4 bytes
+below the stack pointer, because it checks access permissions before it
+adjusts the stack pointer. (Otherwise, the instruction would not be
+restartable in a straightforward fashion.)
+
+@item
+Similarly, the 80@var{x}86 @code{pusha} instruction, which pushes all 32
+bytes of the 8 general-purpose registers at once, may cause a page fault
+32 bytes below the stack pointer.
+
+@item
+Most OSes impose some sort of limit on the stack size. Sometimes it is
+user-adjustable.
+@end itemize
@node Problem 3-1 Page Table Management
@section Problem 3-1: Page Table Management
@itemize @bullet
@item
Some way of translating in software from virtual page frames to
-physical page frames (consider using a hash table---note
-that we provide one in @file{lib/kernel}).
+physical page frames. Consider using a hash table (@pxref{Hash
+Table}).
-@item
-Some way of translating from physical page frames back to virtual
-page frames, so that when you replace a page, you can invalidate
-its translation(s).
+It is possible to do this translation without adding a new data
+structure, by modifying the code in @file{userprog/pagedir.c}. However,
+if you do that you'll need to carefully study and understand section 3.7
+in @bibref{IA32-v3}, and in practice it is probably easier to add a new
+data structure.
@item
Some way of finding a page on disk if it is not in memory. You won't
-need this data structure until part 2, but planning ahead is a good
-idea.
+need this data structure until problem 3-2, but planning ahead is a
+good idea.
+
+You can generalize the virtual-to-physical page table, so that it allows
+you to locate a page wherever it is in physical memory or on disk, or
+you can make this a separate table.
+
+@item
+Some way of translating from physical page frames back to virtual page
+frames, so that when you evict a physical page from its frame, you can
+invalidate its translation(s).
@end itemize
-You need to do the roughly the following to handle a page fault:
+The page fault handler, @func{page_fault} in
+@file{threads/exception.c}, needs to do roughly the following:
@enumerate 1
@item
-Determine the location of the physical page backing the virtual
+Locate the page backing the virtual
address that faulted. It might be in the file system, in swap,
-already be in physical memory and just not set up in the page table,
or it might be an invalid virtual address.
+If you implement sharing, it might even
+already be in physical memory and just not set up in the page table,
-If the virtual address is invalid, that is, if there's no physical
-page backing it, or if the virtual address is above @code{PHYS_BASE},
-meaning that it belongs to the kernel instead of the user, then the
-process's memory access must be disallowed. You should terminate the
-process at this point, being sure to free all of its resources.
+If the virtual address is invalid, that is, if there's nothing
+assigned to go there, or if the virtual address is above
+@code{PHYS_BASE}, meaning that it belongs to the kernel instead of the
+user, then the process's memory access must be disallowed. You should
+terminate the process at this point, being sure to free all of its
+resources.
@item
-If the physical page is not in physical memory, bring it into memory.
+If the page is not in physical memory, fetch it by appropriate means.
If necessary to make room, first evict some other page from memory.
(When you do that you need to first remove references to the page from
any page table that refers to it.)
@item
-Each user process's @code{struct thread} has a @samp{pagedir} member
-that points to its own per-process page directory. Read the PDE for
-the faulting virtual address.
-
-@item
-If the PDE is marked ``not present'' then allocate a new page table
-page and initialize the PDE to point to the new page table. As when
-you allocated a data page, you might have to first evict some other
-page from memory.
-
-@item
-Follow the PDE to the page table. Point the PTE for the faulting
-virtual address to the physical page found in step 2.
+Point the page table entry for the faulting virtual address to the
+physical page. You can use the functions in @file{userprog/pagedir.c}.
@end enumerate
You'll need to modify the ELF loader in @file{userprog/process.c} to
use your new page table management code to construct the page tables
only as page faults occur for them.
+You should use the @func{palloc_get_page} function to get the page
+frames that you use for storing user virtual pages. Be sure to pass
+the @code{PAL_USER} flag to this function when you do so, because that
+allocates pages from a ``user pool'' separate from the ``kernel pool''
+that other calls to @func{palloc_get_page} make.
+
There are many possible ways to implement virtual memory. The above
-is simply an outline of our suggested implementation. You may choose
-any implementation you like, as long as it accomplishes the goal.
+is simply an outline of our suggested implementation.
@node Problem 3-2 Paging To and From Disk
@section Problem 3-2: Paging To and From Disk
Implement paging to and from files and the swap disk. You may use the
-disk on interface @code{hd1:1} as the swap disk.
+disk on interface @code{hd1:1} as the swap disk, using the disk
+interface prototyped in @code{devices/disk.h}. From the @file{vm/build}
+directory, use the command @code{pintos make-disk swap.dsk @var{n}} to
+create an @var{n} MB swap disk named @file{swap.dsk}. Afterward,
+@file{swap.dsk} will automatically be attached when you run
+@command{pintos}.
You will need routines to move a page from memory to disk and from
disk to memory, where ``disk'' is either a file or the swap disk. If
which are not in physical memory, to fully handle page faults. Pages
that you write to swap should not be constrained to be in sequential
order. You will also need a way to track all of the physical memory
-pages, in order to find an unused one when needed, or to evict a page
+pages, to find an unused one when needed, or to evict a page
when memory is needed but no empty pages are available. The data
-structures that you designed in part 1 should do most of the work for
+structures that you designed for problem 3-1 should do most of the work for
you.
You will need a page replacement algorithm. The hardware sets the
-accessed and dirty bits when it accesses memory. Therefore, you
-should be able to take advantage of this information to implement some
-algorithm which attempts to achieve LRU-type behavior. We expect that
-your algorithm perform at least as well as a reasonable implementation
-of the second-chance (clock) algorithm. You will need to show in your
-test cases the value of your page replacement algorithm by
-demonstrating for some workload that it pages less frequently using
-your algorithm than using some inferior page replacement policy. The
-canonical example of a poor page replacement policy is random
-replacement.
+accessed and dirty bits when it accesses memory. You can gain access
+to this information using the functions prototyped in
+@file{userprog/pagedir.h}. You should be able to take advantage of
+this information to implement some algorithm which attempts to achieve
+LRU-type behavior. We expect that your algorithm perform at least as
+well as a reasonable implementation of the second-chance (clock)
+algorithm. You will need to show in your test cases the value of your
+page replacement algorithm by demonstrating for some workload that it
+pages less frequently using your algorithm than using some inferior
+page replacement policy. The canonical example of a poor page
+replacement policy is random replacement.
+
+You must write your code so that we can choose a page replacement
+policy at Pintos startup time. By default, the LRU-like algorithm
+must be in effect, but we must be able to choose random replacement by
+invoking @command{pintos} with the @option{-o random-paging} option.
+Passing this option sets @code{enable_random_paging}, declared in
+@file{threads/init.h}, to true.
Since you will already be paging from disk, you should implement a
``lazy'' loading scheme for new processes. When a process is created,
segments won't change.
There are a few special cases. Look at the loop in
-@code{load_segment()} in @file{userprog/process.c}. Each time
+@func{load_segment} in @file{userprog/process.c}. Each time
around the loop, @code{read_bytes} represents the number of bytes to
read from the executable file and @code{zero_bytes} represents the number
of bytes to initialize to zero following the bytes read. The two
@item
If neither @code{read_bytes} nor @code{zero_bytes} equals
@code{PGSIZE}, then part of the page is to be read from disk and the
-remainder zeroed. This is a special case. You may handle it by
-reading the partial page from disk at executable load time and zeroing
-the rest of the page. This is the only case in which we will allow
-you to load a page in a non-``lazy'' fashion. Many real OSes such as
-Linux do not load partial pages lazily.
+remainder zeroed. This is a special case. You are allowed to handle
+it by reading the partial page from disk at executable load time and
+zeroing the rest of the page. This is the only case in which we will
+allow you to load a page in a non-``lazy'' fashion. Many real OSes
+such as Linux do not load partial pages lazily.
@end itemize
Incidentally, if you have trouble handling the third case above, you
can eliminate it temporarily by linking the test programs with a
-special ``linker script.'' Read @file{tests/userprog/Makefile} for
+special ``linker script.'' Read @file{Makefile.userprog} for
details. We will not test your submission with this special linker
script, so the code you turn in must properly handle all cases.
-You may optionally implement sharing: when multiple processes are
-created that use the same executable file, share read-only pages among
-those processes instead of creating separate copies of read-only
+For extra credit, you may implement sharing: when multiple processes
+are created that use the same executable file, share read-only pages
+among those processes instead of creating separate copies of read-only
segments for each process. If you carefully designed your data
-structures in part 1, sharing of read-only pages should not make this
+structures in problem 3-1, sharing of read-only pages should not make this
part significantly harder.
@node Problem 3-3 Memory Mapped Files
You will need to implement the following system calls:
-@table @asis
+@table @code
@item SYS_mmap
-@itemx bool mmap (int @var{fd}, void *@var{addr}, unsigned @var{length})
+@itemx mapid_t mmap (int @var{fd}, void *@var{addr})
+
+Maps the file open as @var{fd} into the process's virtual address
+space. The entire file is mapped into consecutive virtual pages
+starting at @var{addr}.
+
+If the file's length is not a multiple of @code{PGSIZE}, then some
+bytes in the final mapped page ``stick out'' beyond the end of the
+file. Set these bytes to zero when the page is faulted in from disk,
+and discard them when the page is written back to disk.
-Maps the file open as @var{fd} into the process's address space
-starting at @var{addr} for @var{length} bytes. Returns true if
-successful, false on failure.
+If successful, this function returns a ``mapping ID'' that must
+uniquely identify the mapping within the given process. On failure,
+it must return -1, which otherwise should not be a valid mapping id.
+
+A call to @code{mmap} may fail if the file open as @var{fd} has a
+length of zero bytes. It must fail if @var{addr} is not page-aligned
+or if the range of pages mapped overlaps any existing set of mapped
+pages, including the stack or pages mapped at executable load time.
+
+Your VM system should use the @code{mmap}'d file itself as backing
+store for the mapping. That is, to evict a page mapped by
+@code{mmap}, write it to the file it was mapped from. (In fact, you
+may choose to implement executable mappings as a special case of file
+mappings.)
@item SYS_munmap
-@itemx bool munmap (void *addr, unsigned length)
+@itemx bool munmap (mapid_t @var{mapping})
-Unmaps the segment specified by id. This cannot be used to unmap
-segments mapped by the executable loader. Returns 0 on success, -1 on
-failure. When a file is unmapped, all outstanding changes are written
-to the file, and the segment's pages are removed from the process's
-list of used virtual pages.
+Unmaps the mapping designated by @var{mapping}, which must be a
+mapping ID returned by a previous call to @code{mmap} by the same
+process that has not yet been unmapped.
@end table
-Calls to @code{mmap} must fail if the address is not page-aligned, if
-the length is not positive and a multiple of @var{PGSIZE}. You also
-must error check to make sure that the new segment does not overlap
-already existing segments, and fail if it isn't. If the length passed
-to @code{mmap} is less than the file's length, you should only map the
-first part of the file. If the length passed to @code{mmap} is longer
-than the file, the file should grow to the requested length. Similar
-to the code segment, your VM system should be able to use the
-@code{mmap}'d file itself as backing store for the mmap segment, since
-the changes to the @code{mmap} segment will eventually be written to
-the file. (In fact, you may choose to implement executable mappings
-as a special case of file mappings.)
+All mappings are implicitly unmapped when a process exits, whether via
+@code{exit} or by any other means. When a mapping is unmapped, whether
+implicitly or explicitly, all outstanding changes are written to the
+file, and the pages are removed from the process's list of used
+virtual pages.
@node Virtual Memory FAQ
@section FAQ
Yes.
@item
-@b{How do I use the hash table provided in @file{lib/hash.c}?}
+@anchor{Hash Table}
+@b{How do I use the hash table provided in @file{lib/kernel/hash.c}?}
+
+First, you need to embed a @struct{hash_elem} as a member of the
+object that the hash table will contain. Each @struct{hash_elem} allows
+the object to a member of at most one hash table at a given time. All
+the hash table functions that deal with hash table items actually use
+the address of a @struct{hash_elem}. You can convert a pointer to a
+@struct{hash_elem} member into a pointer to the structure in which
+member is embedded using the @code{hash_entry} macro.
+
+Second, you need to decide on a key type. The key should be something
+that is unique for each object, because a given hash table may not
+contain two objects with equal keys. Then you need to write two
+functions. The first is a @dfn{hash function} that converts a key
+into an integer. Some sample hash functions that you can use or just
+examine are given in @file{lib/kernel/hash.c}. The second function
+needed is a @dfn{comparison function} that compares a pair and returns
+true if the first is less than the second. These two functions have
+to be compatible with the prototypes for @code{hash_hash_func} and
+@code{hash_less_func} in @file{lib/kernel/hash.h}.
+
+Here's a quick example. Suppose you want to put @struct{thread}s
+in a hash table. First, add a @struct{hash_elem} to the thread
+structure by adding a line to its definition:
-FIXME
+@example
+struct hash_elem h_elem; /* Hash table element. */
+@end example
-There are two things you need to use this hashtable:
+We'll choose the @code{tid} member in @struct{thread} as the key,
+and write a hash function and a comparison function:
-1. You need to decide on a key type. The key should be something
-that is unique for each object as inserting two objects with
-the same key will cause the second to overwrite the first.
-(The keys are compared with ==, so you should stick to
-integers and pointers unless you know how to do operator
-overloading.) You also need to write a hash function that
-converts key values to integers, which you will pass into the
-hash table constructor.
+@example
+/* Returns a hash for E. */
+unsigned
+thread_hash (const struct hash_elem *e, void *aux UNUSED)
+@{
+ struct thread *t = hash_entry (e, struct thread, h_elem);
+ return hash_int (t->tid);
+@}
-2. Your key needs to be a field of your object type, and you
-will need to supply a 'get' function that given an object
-returns the key.
+/* Returns true if A's tid is less than B's tid. */
+bool
+thread_less (const struct hash_elem *a_, const struct hash_elem *b_,
+ void *aux UNUSED)
+@{
+ struct thread *a = hash_entry (a_, struct thread, h_elem);
+ struct thread *b = hash_entry (b_, struct thread, h_elem);
+ return a->tid < b->tid;
+@}
+@end example
-Here's a quick example of how to construct a hash table. In
-this table the keys are Thread pointers and the objects are
-integers (you will be using different key/value pairs I'm
-sure). In addition, this hash function is pretty puny. You
-should probably use a better one.
+Then we can create a hash table like this:
@example
-FIXME
-@end example
+struct hash threads;
-and to construct the hash table:
+hash_init (&threads, thread_hash, thread_less, NULL);
+@end example
-HashTable<Thread *, HashObject *> *htable;
+Finally, if @code{@var{t}} is a pointer to a @struct{thread},
+then we can insert it into the hash table with:
-htable = new HashTable<Thread *, HashObject *>(ExtractKeyFromHashObject,
- MyKeyToHashValue);
+@example
+hash_insert (&threads, &@var{t}->h_elem);
+@end example
If you have any other questions about hash tables, the CS109
and CS161 textbooks have good chapters on them, or you can come
to any of the TA's office hours for further clarification.
+@item
+@b{What are the @var{aux} parameters to the hash table functions good
+for?}
+
+In simple cases you won't have any need for the @var{aux} parameters.
+In these cases you can just pass a null pointer to @func{hash_init}
+for @var{aux} and ignore the values passed to the hash function and
+comparison functions. (You'll get a compiler warning if you don't use
+the @var{aux} parameter, but you can turn that off with the
+@code{UNUSED} macro, as shown above, or you can just ignore it.)
+
+@var{aux} is useful when you have some property of the data in the
+hash table that's both constant and needed for hashing or comparisons,
+but which is not stored in the data items themselves. For example, if
+the items in a hash table contain fixed-length strings, but the items
+themselves don't indicate what that fixed length is, you could pass
+the length as an @var{aux} parameter.
+
@item
@b{The current implementation of the hash table does not do something
that we need it to do. What gives?}
The linker is responsible for the layout of a user program in
memory. The linker is directed by a ``linker script'' which tells it
-the names and locations of the various program segments. The
-test/script and testvm/script files are the linker scripts for the
-multiprogramming and virtual memory assignments respectively. You can
+the names and locations of the various program segments. You can
learn more about linker scripts by reading the ``Scripts'' chapter in
the linker manual, accessible via @samp{info ld}.
-
-@item Page Table Management FAQs
-@enumerate 1
-@item
-@b{Do page tables need to created lazily?}
-
-No. You can create the page tables at load time (or @code{mmap} time)
-if you like.
-
-@item
-@b{Our code handles the PageFault exceptions. However, the number of
-page faults handled does not show up in the final stats output. Is
-there a counter that we must increment to correct this problem?}
-
-FIXME
-
-Yes, you'll need to update kernel->stats->numPageFaults when
-you handle a page fault in your code.
@end enumerate
-@item Paging FAQs
-
-@enumerate 1
-@item
-@item
-@b{Does the virtual memory system need to support growth of the stack
-segment?}
-
-Yes. If a page fault appears just below the last stack segment page,
-you must add a new page to the bottom of the stack. It is impossible
-to predict how large the stack will grow at compile time, so we must
-allocate pages as necessary. You should only allocate additional pages
-if they ``appear'' to be stack accesses.
-
-@item
-@b{Does the first stack page need to be loaded lazily?}
+@menu
+* Problem 3-1 and 3-2 FAQ::
+* Problem 3-3 Memory Mapped File FAQ::
+@end menu
-No, you can initialize the first stack page with the command line at
-load time. There's no need to wait for it to be faulted in. Even if
-you did wait, the very first instruction in the user program is likely
-to be one that faults in the page.
+@node Problem 3-1 and 3-2 FAQ
+@subsection Problem 3-1 and 3-2 FAQ
+@enumerate 1
@item
@b{Does the virtual memory system need to support growth of the data
segment?}
No. The size of the data segment is determined by the linker. We
still have no dynamic allocation in Pintos (although it is possible to
-``fake'' it at the user level by using memory-mapped files).
-Implementing @code{sbrk()} has been an extra-credit assignment in
-previous years, but adds little additional complexity to a
+``fake'' it at the user level by using memory-mapped files). However,
+implementing it would add little additional complexity to a
well-designed system.
@item
-@b{But what do you mean by ``appear'' to be stack accesses? How big can a
-stack growth be? Under what circumstances do we grow the stack?}
-
-If it looks like a stack request, then you grow the stack. Yes, that's
-ambiguous. You need to make a reasonable decision about what looks
-like a stack request. For example, you could decide a page, or two
-pages, or ten pages, or more@enddots{} Or, you could use some other
-heuristic to figure this out.
+@b{Why do I need to pass @code{PAL_USER} to @func{palloc_get_page}
+when I allocate physical page frames?}@anchor{Why PAL_USER?}
-Make a reasonable decision and document it in your code and in
-your design document. Please make sure to justify your decision.
-
-@item
-@b{How big should the file(s) we're using as a backing store for memory
-be?}
-
-These files will need to be able to grow based on the number of pages
-you're committed to storing on behalf of the processes currently in
-memory. They should be able to grow to the full size of the disk.
+You can layer some other allocator on top of @func{palloc_get_page}
+if you like, but it should be the underlying mechanism, directly or
+indirectly, for two reasons. First, running out of pages in the user
+pool just causes user programs to page, but running out of pages in
+the kernel pool will cause all kinds of problems, because many kernel
+functions depend on being able to allocate memory. Second, you can
+use the @option{-ul} option to @command{pintos} to limit the size of
+the user pool, which makes it easy to test your VM implementation with
+various user memory sizes.
@end enumerate
-@item Memory Mapped File FAQs
+@node Problem 3-3 Memory Mapped File FAQ
+@subsection Problem 3-3: Memory Mapped File FAQ
@enumerate 1
@item
@b{How do we interact with memory-mapped files?}
Let's say you want to map a file called @file{foo} into your address
-space at address @t{0x10000000}. You open the file, determine its
-length, and then use Mmap:
+space at address @t{0x10000000}. You open the file then use @code{mmap}:
@example
#include <stdio.h>
@{
void *addr = (void *) 0x10000000;
int fd = open ("foo");
- int length = filesize (fd);
- if (mmap (fd, addr, length))
+ mapid_t map = mmap (fd, addr);
+ if (map != -1)
printf ("success!\n");
@}
@end example
it:
@example
-munmap (addr);
+munmap (map);
@end example
@item
-@b{What if two processes memory-map the same file?}
+@b{What if two processes map the same file into memory?}
There is no requirement in Pintos that the two processes see
-consistent data. Unix handles this by making the processes share the
+consistent data. Unix handles this by making the two mappings share the
same physical page, but the @code{mmap} system call also has an
argument allowing the client to specify whether the page is shared or
private (i.e.@: copy-on-write).
@item
@b{What happens if a user removes a @code{mmap}'d file?}
-@item
-You should follow the Unix convention and the mapping should still be
-valid. This is similar to the question in the User Programs FAQ about
-a process with a file descriptor to a file that has been removed.
+The mapping should remain valid, following the Unix convention.
+@xref{Removing an Open File}, for more information.
@item
@b{What if a process writes to a page that is memory-mapped, but the
location written to in the memory-mapped page is past the end
of the memory-mapped file?}
-Can't happen. @code{mmap} extends the file to the requested length,
-and Pintos provides no way to shorten a file. You can remove a file,
-but the mapping remains valid (see the previous question).
+Can't happen. @code{mmap} maps an entire file and Pintos provides no
+way to shorten a file. (Until project 4, there's no way to extend a
+file either.) You can remove a file, but the mapping remains valid
+(see the previous question).
@item
@b{Do we have to handle memory mapping @code{stdin} or @code{stdout}?}
user attempts to memory map a file descriptor for the console device.
@item
-@b{What happens when a process exits with mmap'd files?}
-
-When a process finishes each of its @code{mmap}'d files is implicitly
-unmapped. When a process @code{mmap}s a file and then writes into the
-area for the file it is making the assumption the changes will be
-written to the file.
+@b{If a user closes a mapped file, should it be automatically
+unmapped?}
-@item
-@b{If a user closes a mmaped file, should be automatically unmap it
-for them?}
-
-No, once created the mapping is valid until @code{munmap} is called
+No. Once created the mapping is valid until @code{munmap} is called
or the process exits.
@end enumerate
-@end enumerate
-
-TLB invalidation FIXME
projects / pintos-anon / blobdiff