Alternatively, the kernel could avoid the problem by only accessing user
data through the user virtual address.
+Other aliases should only arise if you implement sharing, as extra
+credit (@pxref{VM Extra Credit}), or as bugs elsewhere in your code.
+
@deftypefun bool pagedir_is_dirty (uint32_t *@var{pd}, const void *@var{vpage})
@deftypefunx bool pagedir_is_accessed (uint32_t *@var{pd}, const void *@var{vpage})
Returns true if page directory @var{pd} contains a page table entry for
@itemize @bullet
@item
Some way of translating in software from virtual page frames to
-physical page frames. Consider using a hash table (@pxref{Hash
-Table}).
+physical page frames. Pintos provides a hash table that you may find
+useful for this purpose (@pxref{Hash Table}).
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
+if you do that you'll need to carefully study and understand section
+3.7, ``Page Translation Using 32-Bit Physical Addressing,'' in
+@bibref{IA32-v3a}, and in practice it is probably easier to add a new
data structure.
@item
executing and other page faults that do not require I/O should be able to
complete. These criteria require some synchronization effort.
-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{-rndpg} option. Passing this option
-sets @code{enable_random_paging}, declared in @file{threads/init.h}, to
-true.
-
@node Lazy Loading
@subsection Lazy Loading
Implement stack growth. In project 2, the stack was a single page at
the top of the user virtual address space, and programs were limited to
that much stack. Now, if the stack grows past its current size,
-allocate additional page as necessary.
+allocate additional pages as necessary.
Allocate additional pages only if they ``appear'' to be stack accesses.
Devise a heuristic that attempts to distinguish stack accesses from
-other accesses. You can retrieve the user program's current stack
-pointer from the @struct{intr_frame}'s @code{esp} member.
+other accesses.
User programs are buggy if they write to the stack below the stack
pointer, because typical real OSes may interrupt a process at any time
@code{PUSHA} instruction pushes 32 bytes at once, so it can fault 32
bytes below the stack pointer.
+You will need to be able to obtain the current value of the user
+program's stack pointer. Within a system call or a page fault generated
+by a user program, you can retrieve it from @code{esp} member of the
+@struct{intr_frame} passed to @func{syscall_handler} or
+@func{page_fault}, respectively. If you verify user pointers before
+accessing them (@pxref{Accessing User Memory}), these are the only cases
+you need to handle. On the other hand, if you depend on page faults to
+detect invalid memory access, you will need to handle another case,
+where a page fault occurs in the kernel. Reading @code{esp} out of the
+@struct{intr_frame} passed to @func{page_fault} in that case will obtain
+the kernel stack pointer, not the user stack pointer. You will need to
+arrange another way, e.g.@: by saving @code{esp} into @struct{thread} on
+the initial transition from user to kernel mode.
+
You may impose some absolute limit on stack size, as do most OSes.
-(Some OSes make the limit user-adjustable, e.g.@: with the
-@command{ulimit} command on many Unix systems.)
+Some OSes make the limit user-adjustable, e.g.@: with the
+@command{ulimit} command on many Unix systems. On many GNU/Linux systems,
+the default limit is 8 MB.
The first stack page need not be allocated lazily. You can initialize
it with the command line arguments at load time, with no need to wait
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.
+A partial page need not be lazily loaded, as in the case of a partial
+page in an executable (@pxref{Lazy Loading}).
If successful, this function returns a ``mapping ID'' that
uniquely identifies the mapping within the process. On failure,
written back to the file, and pages not written must not be. The pages
are then removed from the process's list of virtual pages.
+Closing or removing a file does not unmap any of its mappings. Once
+created, a mapping is valid until @code{munmap} is called or the process
+exits, following the Unix convention. @xref{Removing an Open File}, for
+more information.
+
+If two or more processes map the same file, there is no requirement that
+they see 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).
+
@node Project 3 FAQ
@section FAQ
@command{diffstat} program. The final row gives total lines inserted
and deleted; a changed line counts as both an insertion and a deletion.
-This summary is relative to the Pintos base code, but we started from
-the reference solution to project 2. @xref{Project 2 FAQ}, for the
-summary of project 2.
+This summary is relative to the Pintos base code, but the reference
+solution for project 3 starts from the reference solution to project 2.
+@xref{Project 2 FAQ}, for the summary of project 2.
+
+The reference solution represents just one possible solution. Many
+other solutions are also possible and many of those differ greatly from
+the reference solution. Some excellent solutions may not modify all the
+files modified by the reference solution, and some may modify files not
+modified by the reference solution.
@verbatim
Makefile.build | 4
17 files changed, 1532 insertions(+), 104 deletions(-)
@end verbatim
-@item Do we need a working HW 2 to implement HW 3?
+@item Do we need a working Project 2 to implement Project 3?
Yes.
-@item How do I use the hash table provided in @file{lib/kernel/hash.c}?
-@anchor{Hash Table}
-
-First, you need to add 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 needed
-function is a @dfn{comparison function} that compares a pair of objects
-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:
-
-@example
-struct hash_elem h_elem; /* Hash table element. */
-@end example
-
-We'll choose the @code{tid} member in @struct{thread} as the key,
-and write a hash function and a comparison function:
-
-@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);
-@}
-
-/* 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
-
-Then we can create a hash table like this:
-
-@example
-struct hash threads;
-
-hash_init (&threads, thread_hash, thread_less, NULL);
-@end example
-
-Finally, if @code{@var{t}} is a pointer to a @struct{thread},
-then we can insert it into the hash table with:
-
-@example
-hash_insert (&threads, &@var{t}->h_elem);
-@end example
-
-The CS109 and CS161 textbooks have chapters on hash tables.
-
-@item Why do the hash table functions have @var{aux} parameters?
-
-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 Can we change the hash table implementation?
-
-You are welcome to modify it. It is not used by any of the code we
-provided, so modifying it won't affect any code but yours. Do
-whatever it takes to make it work the way you want.
-
@item What extra credit is available?
+@anchor{VM Extra Credit}
You may implement sharing: when multiple processes are created that use
the same executable file, share read-only pages among those processes
You can layer some other allocator on top of @func{palloc_get_page} if
you like, but it should be the underlying mechanism.
-Also, you can use the @option{-u} option to @command{pintos} to limit
+Also, 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.
+
+@item Data pages might need swap space. Can I swap them out at process load?
+
+No. Reading data pages from the executable and writing them to swap
+immediately at program startup is not demand paging. You need to demand
+page everything (except partial pages).
@end table
@node Memory Mapped File FAQ
it like so:
@example
-write (addr, 64, STDOUT_FILENO);
+write (STDOUT_FILENO, addr, 64);
@end example
Similarly, if you wanted to replace the first byte of the file,
The @command{mcp} program in @file{src/examples} shows how to copy a
file using memory-mapped I/O.
-
-@item 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 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 What happens if a user removes a @code{mmap}'d file?
-
-The mapping should remain valid, following the Unix convention.
-@xref{Removing an Open File}, for more information.
-
-@item If a user closes a mapped file, should it be automatically unmapped?
-
-No. Once created the mapping is valid until @code{munmap} is called
-or the process exits.
@end table
projects / pintos-anon / blobdiff