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 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.
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
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.
+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
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 evict a physical page from its frame, 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 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
The page fault handler, @func{page_fault} in
@item
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 nothing
assigned to go there, or if the virtual address is above
Implement paging to and from files and the swap disk. You may use the
disk on interface @code{hd1:1} as the swap disk, using the disk
-interface prototyped in @code{devices/disk.h}.
+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
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,
it will not run immediately. Therefore, it doesn't make sense to load
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.
@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 address space
-starting at @var{addr} for @var{length} bytes. Returns true if
-successful, false on failure. Failure cases include the following:
+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}.
-@itemize @bullet
-@item
-@var{addr} is not page-aligned.
-
-@item
-@var{length} is not positive.
-
-@item
-The range of pages mapped overlaps any existing set of mapped pages,
-including the stack or pages mapped at executable load time.
-@end itemize
-
-@var{length} is treated as if it were rounded up to the nearest
-multiple of the page size, that is, as if the first statement in the
-system call's implementation were
-@example
-length = ROUND_UP (length, PGSIZE);
-@end example
-(The @code{ROUND_UP} macro is defined in @file{<round.h>}.)
-The remainder of this description assumes that this has been done.
-
-If @var{length} is less than @var{fd}'s length, you should only map
-the first @var{length} bytes of the file. If @var{length} is greater
-than @var{fd}'s length, when the file's length is also rounded up to a
-page multiple, the call should fail. Ideally it would extend the
-file, but our file system does not yet support growing files.
-
-If @var{length} is greater than @var{fd}'s (unrounded) length, then some
+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.
+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.
-Your VM system should use the @code{mmap}'d file itself as
-backing store for the mapped segment. That is, to evict a page mapped by
-@code{mmap} must be evicted, 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.)
+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.
-@item SYS_munmap
-@itemx bool munmap (void *addr, unsigned length)
+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.
-Unmaps @var{length} bytes starting at @var{addr}. Returns true on
-success, false on failure. Failure cases include the following:
+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.)
-@itemize @bullet
-@item
-@var{addr} is not page-aligned.
-
-@item
-@var{length} is not positive.
-
-@item
-One or more pages within the range to be unmapped were not mapped
-using the @code{mmap} system call.
-@end itemize
-
-As with @code{mmap}, @var{length} is treated as if it were rounded up
-to the nearest multiple of the page size.
+@item SYS_munmap
+@itemx bool munmap (mapid_t @var{mapping})
-It is valid to unmap only some of the pages that were mapped in a
-previous system call.
+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
All mappings are implicitly unmapped when a process exits, whether via
-@code{exit} or by any other means. When a file is unmapped, whether
+@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.
@anchor{Hash Table}
@b{How do I use the hash table provided in @file{lib/kernel/hash.c}?}
-First, you need to embed a @code{hash_elem} object as a member of the
-object that the hash table will contain. Each @code{hash_elem} allows
+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 @code{hash_elem}. You can convert a pointer to a
-@code{hash_elem} member into a pointer to the structure in which
+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
@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 @code{hash_elem} to the thread
+in a hash table. First, add a @struct{hash_elem} to the thread
structure by adding a line to its definition:
@example
-hash_elem h_elem; /* Hash table element. */
+struct hash_elem h_elem; /* Hash table element. */
@end example
We'll choose the @code{tid} member in @struct{thread} as the key,
@example
/* Returns a hash for E. */
unsigned
-thread_hash (const hash_elem *e, void *aux UNUSED)
+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);
/* Returns true if A's tid is less than B's tid. */
bool
-thread_less (const hash_elem *a_, const hash_elem *b_,
+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);
@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 @code{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, length);
+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?}
-You should follow the Unix convention and the mapping should still be
-valid. @xref{Removing an Open File}, for more information.
+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} checks that the mapped region is within the
-file's length 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).
+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}?}
neither of these properties, @code{mmap} should return false when the
user attempts to memory map a file descriptor for the console device.
-@item
-@b{What happens when a process exits with mapped files?}
-
-When a process finishes, each of its mapped 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.
-
@item
@b{If a user closes a mapped file, should it be automatically
unmapped?}
-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
projects / pintos-anon / blobdiff