You will continue to handle Pintos disks and file systems the same way
you did in the previous assignment (@pxref{Using the File System}).
-The tests for project 3 (and later projects) will probably run faster if
-you use the qemu emulator, e.g.@: via @code{make check
-PINTOSOPTS='--qemu'}.
-
@menu
* Project 3 Background::
* Project 3 Suggested Order of Implementation::
You will probably be encountering just a few files 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. You will use this interface to access the swap disk.
+@item devices/block.h
+@itemx devices/block.c
+Provides sector-based read and write access to block device. You will
+use this interface to access the swap partition as a block device.
@end table
@node Memory Terminology
@node Pages
@subsubsection Pages
-A @dfn{page}, sometimes called a @dfn{virtual page}, is a contiguous
+A @dfn{page}, sometimes called a @dfn{virtual page}, is a continuous
region of virtual memory 4,096 bytes (the @dfn{page size}) in length. A
page must be @dfn{page-aligned}, that is, start on a virtual address
evenly divisible by the page size. Thus, a 32-bit virtual address can
@subsubsection Frames
A @dfn{frame}, sometimes called a @dfn{physical frame} or a @dfn{page
-frame}, is a contiguous region of physical memory. Like pages, frames
+frame}, is a continuous region of physical memory. Like pages, frames
must be page-size and page-aligned. Thus, a 32-bit physical address can
be divided into a 20-bit @dfn{frame number} and a 12-bit @dfn{frame
offset} (or just @dfn{offset}), like this:
@example
@group
- +----------+
- .--------------->|Page Table|-----------.
- / +----------+ |
- 0 | 12 11 0 0 V 12 11 0
- +---------+----+ +---------+----+
- |Page Nr | Ofs| |Frame Nr | Ofs|
- +---------+----+ +---------+----+
- Virt Addr | Phys Addr ^
- \_______________________________________/
+ +----------+
+ .--------------->|Page Table|---------.
+ / +----------+ |
+ 31 | 12 11 0 31 V 12 11 0
+ +-----------+-------+ +------------+-------+
+ | Page Nr | Ofs | | Frame Nr | Ofs |
+ +-----------+-------+ +------------+-------+
+ Virt Addr | Phys Addr ^
+ \_____________________________________/
@end group
@end example
@node Swap Slots
@subsubsection Swap Slots
-A @dfn{swap slot} is a contiguous, page-size region of disk space on the
-swap disk. Although hardware limitations dictating the placement of
+A @dfn{swap slot} is a continuous, page-size region of disk space in the
+swap partition. Although hardware limitations dictating the placement of
slots are looser than for pages and frames, swap slots should be
page-aligned because there is no downside in doing so.
@table @asis
@item Supplemental page table
-Enables page fault handling by supplementing the page table.
+Enables page fault handling by supplementing the hadrware page table.
@xref{Managing the Supplemental Page Table}.
@item Frame table
file or swap. You will have to implement a more sophisticated page
fault handler to handle these cases. Your page fault handler, which you
should implement by modifying @func{page_fault} in
-@file{threads/exception.c}, needs to do roughly the following:
+@file{userprog/exception.c}, needs to do roughly the following:
@enumerate 1
@item
you implement sharing, the page's data might even already be in a page
frame, but not in the page table.
-If the page is unmapped, that is, if there's no data there, or if the
+If the supplemental page table indicates that the user process should
+not expect any data at the address it was trying to access, or if the
page lies within kernel virtual memory, or if the access is an attempt
to write to a read-only page, then the access is invalid. Any invalid
access terminates the process and thereby frees all of its resources.
The most important operation on the frame table is obtaining an unused
frame. This is easy when a frame is free. When none is free, a frame
-must be made free by evicting some page from its frame. If no frame can
-be evicted without allocating a swap slot, but swap is full, some
-process must be killed to free memory (the choice of process to kill is
-up to you).
+must be made free by evicting some page from its frame.
+
+If no frame can be evicted without allocating a swap slot, but swap is
+full, panic the kernel. Real OSes apply a wide range of policies to
+recover from or prevent such situations, but these policies are beyond
+the scope of this project.
The process of eviction comprises roughly the following steps:
The swap table tracks in-use and free swap slots. It should allow
picking an unused swap slot for evicting a page from its frame to the
-swap disk. It should allow freeing a swap slot when its page is read
+swap partition. It should allow freeing a swap slot when its page is read
back or the process whose page was swapped is terminated.
-You may use the disk on interface @code{hd1:1} as the swap disk, using
-the disk interface prototyped in @code{devices/disk.h}. From the
+You may use the @code{BLOCK_SWAP} block device for swapping, obtaining
+the @struct{block} that represents it by calling @func{block_get_role}.
+From the
@file{vm/build} directory, use the command @code{pintos-mkdisk swap.dsk
-@var{n}} to create an @var{n} MB swap disk named @file{swap.dsk}.
-Afterward, @file{swap.dsk} will automatically be attached as
-@code{hd1:1} when you run @command{pintos}. Alternatively, you can tell
+--swap-size=@var{n}} to create an disk named @file{swap.dsk} that
+contains a @var{n}-MB swap partition.
+Afterward, @file{swap.dsk} will automatically be attached as an extra disk
+when you run @command{pintos}. Alternatively, you can tell
@command{pintos} to use a temporary @var{n}-MB swap disk for a single
-run with @option{--swap-disk=@var{n}}.
+run with @option{--swap-size=@var{n}}.
Swap slots should be allocated lazily, that is, only when they are
actually required by eviction. Reading data pages from the executable
what functionality we require your OS to support. We will expect
you to come up with a design that makes sense. You will have the
freedom to choose how to handle page faults, how to organize the swap
-disk, how to implement paging, etc.
+partition, how to implement paging, etc.
@menu
* Project 3 Design Document::
swap because they can always be read back from the executable.
Implement a global page replacement algorithm that approximates LRU.
-Your algorithm should perform at least as well as the ``second chance''
-or ``clock'' algorithm.
+Your algorithm should perform at least as well as the simple variant
+of the ``second chance'' or ``clock'' algorithm.
Your design should allow for parallelism. If one page fault requires
I/O, in the meantime processes that do not fault should continue
@itemize @bullet
@item
If @code{page_read_bytes} equals @code{PGSIZE}, the page should be demand
-paged from disk on its first access.
+paged from the underlying file on its first access.
@item
If @code{page_zero_bytes} equals @code{PGSIZE}, the page does not need to
@item
Otherwise, neither @code{page_read_bytes} nor @code{page_zero_bytes}
equals @code{PGSIZE}. In this case, an initial part of the page is to
-be read from disk and the remainder zeroed.
+be read from the underlying file and the remainder zeroed.
@end itemize
@node Stack Growth
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
+by a user program, you can retrieve it from the @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.
+where a page fault occurs in the kernel. Since the processor only
+saves the stack pointer when an exception causes a switch from user
+to kernel mode, reading @code{esp} out of the @struct{intr_frame}
+passed to @func{page_fault} would yield an undefined value, not the
+user stack pointer. You will need to arrange another way, such as
+saving @code{esp} into @struct{thread} on the initial transition
+from user to kernel mode.
+
+You should 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. 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
-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.)
+The first stack page need not be allocated lazily. You can allocate
+and initialize it with the command line arguments at load time, with
+no need to wait for it to be faulted in.
All stack pages should be candidates for eviction. An evicted stack
page should be written to swap.
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,
+@code{mmap}ed 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,
+file. Set these bytes to zero when the page is faulted in from the
+file system,
and discard them when the page is written back to disk.
If successful, this function returns a ``mapping ID'' that
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.
+more information. You should use the @code{file_reopen} function to
+obtain a separate and independent reference to the file for each of
+its mappings.
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
an argument allowing the client to specify whether the page is shared or
private (i.e.@: copy-on-write).
+@subsection Accessing User Memory
+You will need to adapt your code to access user memory (@pxref{Accessing
+User Memory}) while handling a system call. Just as user processes may
+access pages whose content is currently in a file or in swap space, so
+can they pass addresses that refer to such non-resident pages to system
+calls. Moreover, unless your kernel takes measures to prevent this,
+a page may be evicted from its frame even while it is being accessed
+by kernel code. If kernel code accesses such non-resident user pages,
+a page fault will result.
+
+While accessing user memory, your kernel must either be prepared to handle
+such page faults, or it must prevent them from occurring. The kernel
+must prevent such page faults while it is holding resources it would
+need to acquire to handle these faults. In Pintos, such resources include
+locks acquired by the device driver(s) that control the device(s) containing
+the file system and swap space. As a concrete example, you must not
+allow page faults to occur while a device driver accesses a user buffer
+passed to @code{file_read}, because you would not be able to invoke
+the driver while handling such faults.
+
+Preventing such page faults requires cooperation between the code within
+which the access occurs and your page eviction code. For instance,
+you could extend your frame table to record when a page contained in
+a frame must not be evicted. (This is also referred to as ``pinning''
+or ``locking'' the page in its frame.) Pinning restricts your page
+replacement algorithm's choices when looking for pages to evict, so be
+sure to pin pages no longer than necessary, and avoid pinning pages when
+it is not necessary.
+
@node Project 3 FAQ
@section FAQ
sharing of read-only pages should not make this part significantly
harder.
+@item How do we resume a process after we have handled a page fault?
+
+Returning from @func{page_fault} resumes the current user process
+(@pxref{Internal Interrupt Handling}).
+It will then retry the instruction to which the instruction pointer points.
+
+@item Why do user processes sometimes fault above the stack pointer?
+
+You might notice that, in the stack growth tests, the user program faults
+on an address that is above the user program's current stack pointer,
+even though the @code{PUSH} and @code{PUSHA} instructions would cause
+faults 4 and 32 bytes below the current stack pointer.
+
+This is not unusual. The @code{PUSH} and @code{PUSHA} instructions are
+not the only instructions that can trigger user stack growth.
+For instance, a user program may allocate stack space by decrementing the
+stack pointer using a @code{SUB $n, %esp} instruction, and then use a
+@code{MOV ..., m(%esp)} instruction to write to a stack location within
+the allocated space that is @var{m} bytes above the current stack pointer.
+Such accesses are perfectly valid, and your kernel must grow the
+user program's stack to allow those accesses to succeed.
+
@item Does the virtual memory system need to support data segment growth?
No. The size of the data segment is determined by the linker. We still
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{-ul} option to @command{pintos} to limit
+Also, you can use the @option{-ul} kernel command-line option to limit
the size of the user pool, which makes it easy to test your VM
implementation with various user memory sizes.
@end table
projects / pintos-anon / blobdiff