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
-data structure.
+You don't strictly need a new data structure for this. You could
+instead modify the code in @file{userprog/pagedir.c}. If you do that
+you'll need to thoroughly understand how 80@var{x}86 page tables work
+by, e.g.,@: studying section 3.7, ``Page Translation Using 32-Bit
+Physical Addressing,'' in @bibref{IA32-v3a}. In practice, most groups
+use a separate data structure.
@item
Some way of finding a page on disk (in a file or in swap) if it is not
perform at least as well as the ``second chance'' or ``clock''
algorithm.
-Your design should allow for parallelism. Multiple processes should
-be able to process page faults at once. If one page fault require
+Your design should allow for parallelism. If one page fault requires
I/O, in the meantime processes that do not fault should continue
-executing and other page faults that do not require I/O should be able to
-complete. These criteria require some synchronization effort.
+executing and other page faults that do not require I/O should be able
+to complete. These criteria require some synchronization effort.
@node Lazy Loading
@subsection Lazy Loading
The core of the program loader is the loop in @func{load_segment} in
@file{userprog/process.c}.
-Each time around the loop, @code{read_bytes} receives the number of
-bytes to read from the executable file and @code{zero_bytes} receives
+Each time around the loop, @code{page_read_bytes} receives the number of
+bytes to read from the executable file and @code{page_zero_bytes} receives
the number of bytes to initialize to zero following the bytes read. The
two always sum to @code{PGSIZE} (4,096). The handling of a page depends
on these variables' values:
@itemize @bullet
@item
-If @code{read_bytes} equals @code{PGSIZE}, the page should be demand
+If @code{page_read_bytes} equals @code{PGSIZE}, the page should be demand
paged from disk on its first access.
@item
-If @code{zero_bytes} equals @code{PGSIZE}, the page does not need to
+If @code{page_zero_bytes} equals @code{PGSIZE}, the page does not need to
be read from disk at all because it is all zeroes. You should handle
such pages by creating a new page consisting of all zeroes at the
first page fault.
@item
-If neither @code{read_bytes} nor @code{zero_bytes} equals
+If neither @code{page_read_bytes} nor @code{page_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 are allowed to handle
it by reading the partial page from disk at executable load time and
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
space. The entire file is mapped into consecutive virtual pages
starting at @var{addr}.
+Your VM system must lazily load pages in @code{mmap} regions and use the
+@code{mmap}'d file itself as backing store for the mapping. That is,
+evicting a page mapped by @code{mmap} writes it back to the file it was
+mapped from.
+
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,
It must also fail if @var{addr} is 0, because some Pintos code assumes
virtual page 0 is not mapped. Finally, file descriptors 0 and 1,
representing console input and output, are not mappable.
-
-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 special, copy-on-write
-file mappings.)
@end deftypefn
@deftypefn {System Call} void munmap (mapid_t @var{mapping})
@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.
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.
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,