Operating System辅导CSE421 Component In Pintos讲解R、R程序讲解

Preparation

Before beginning your work, please read the following carefully:

Chapters 8-9 from Silberschatz
Lecture slides on Memory and Virtual Memory
Pintos Introduction
Pintos Reference Guide
Complete Pintos Documentation (PDF file) – for reference only

Task: Implement User Programs in Pintos OS

In this project, you are asked to perform “kernel” level programming of the User Programs component in the Pintos operation system. The base code already supports loading and running user programs, but no I/O or interactivity is possible. In this project, you will enable programs to interact with the OS via system calls.

Setting Up The Pintos Environment

Project-2 does not depend on project-1. No code from project-1 is required for this assignment. So, you can choose to continue working on your existing code base, or you can fetch a clean copy of the Pintos source code (especially if you think you have messed up in project-1).
If you want to continue working on your existing code base, please jump to Section 3 – Implementation of the Project. Otherwise, follow the steps below if you want to get a clean copy of the Pintos source code:
Set up Pintos on departmental servers (i.e. timberlake) by following the detailed instructions from the “How to configure Pintos on Timberlake” post on Piazza under Resources. Please follow these instructions very carefully (line by line) to install and run Pintos without any problems.
To learn how to run, debug and test Pintos code, please read the Section 1 [Pintos Introduction from Pintos Manual.

Implementation of the Project

You will be working primarily in the “userprog” directory of the source tree for this assignment. Compilation should be done in the “userprog” directory.

Background

Up to now, all of the code you have run under Pintos has been part of the operating system kernel. This means, for example, that all the test code from the last assignment ran as part of the kernel, with full access to privileged parts of the system. Once we start running user programs on top of the operating system, this is no longer true. This project deals with the consequences.
We allow more than one process to run at a time. Each process has one thread (multi-threaded processes are not supported). User programs are written under the illusion that they have the entire machine. This means that when you load and run multiple processes at a time, you must manage memory, scheduling, and other state correctly to maintain this illusion.
In the previous project, we compiled our test code directly into your kernel, so we had to require specific function interfaces within the kernel. From now on, we will test your operating system by running user programs. This gives you much greater freedom. You must make sure that the user program interface meets the specifications described here, but given that constraint you are free to restructure or rewrite kernel code however you wish.

Source Files

The easiest way to get an overview of the programming you will be doing is to simply go over each part you’ll be working with. In ‘userprog’, you’ll find a small number of files, but here is where the bulk of your work will be:

‘process.c’
‘process.h’
Loads ELF binaries and starts processes.
‘pagedir.c’
‘pagedir.h’
A simple manager for 80x86 hardware page tables. Although you probably won’t want to modify this code for this project, you may want to call some of its functions.
‘syscall.c’
‘syscall.h’
Whenever a user process wants to access some kernel functionality, it invokes a system call. This is a skeleton system call handler. Currently, it just prints a message and terminates the user process. In part 2 of this project you will add code to do everything else needed by system calls.
‘exception.c’
‘exception.h’
When a user process performs a privileged or prohibited operation, it traps into the kernel as an “exception” or “fault.”1 These files handle exceptions. Currently all exceptions simply print a message and terminate the process. Some, but not all, solutions to project 2 require modifying page_fault() in this file.
‘gdt.c’
‘gdt.h’
The 80x86 is a segmented architecture. The Global Descriptor Table (GDT) is a table that describes the segments in use. These files set up the GDT. You should not need to modify these files for any of the projects. You can read the code if you’re interested in how the GDT works.
‘tss.c’
‘tss.h’
The Task-State Segment (TSS) is used for 80x86 architectural task switching. Pintos uses the TSS only for switching stacks when a user process enters an interrupt handler, as does Linux. You should not need to modify these files for any of the projects. You can read the code if you’re interested in how the TSS works.

Using the File System

You will need to interface to the file system code for this project, because user programs are loaded from the file system and many of the system calls you must implement deal with the file system. However, the focus of this project is not the file system, so we have provided a simple but complete file system in the ‘filesys’ directory. You will want to look over the ‘filesys.h’ and ‘file.h’ interfaces to understand how to use the file system, and especially its many limitations.
There is no need to modify the file system code for this project, and so we recommend that you do not. Working on the file system is likely to distract you from this project’s focus.
You will have to tolerate the following limitations of the file system:

No internal synchronization. Concurrent accesses will interfere with one another. You should use synchronization to ensure that only one process at a time is executing file system code.
File size is fixed at creation time. The root directory is represented as a file, so the number of files that may be created is also limited.
File data is allocated as a single extent, that is, data in a single file must occupy a contiguous range of sectors on disk. External fragmentation can therefore become a serious problem as a file system is used over time.
No subdirectories.
File names are limited to 14 characters.
A system crash mid-operation may corrupt the disk in a way that cannot be repaired automatically. There is no file system repair tool anyway.

One important feature is included:

Unix-like semantics for filesys_remove() are implemented. That is, if a file is open when it is removed, its blocks are not deallocated and it may still be accessed by any threads that have it open, until the last one closes it.

You need to be able to create a simulated disk with a file system partition. The pintos-mkdisk program provides this functionality. From the ‘userprog/build’ directory, execute pintos-mkdisk filesys.dsk –filesys-size=2. This command creates a simulated disk named ‘filesys.dsk’ that contains a 2 MB Pintos file system partition. Then format the file system partition by passing ‘-f -q’ on the kernel’s command line: pintos -f -q. The ‘-f’ option causes the file system to be formatted, and ‘-q’ causes Pintos to exit as soon as the format is done.
You’ll need a way to copy files in and out of the simulated file system. The pintos ‘-p’ (“put”) and ‘-g’ (“get”) options do this. To copy ‘file’ into the Pintos file system, use the command ‘pintos -p file – -q’. (The ‘–’ is needed because ‘-p’ is for the pintos script, not for the simulated kernel.) To copy it to the Pintos file system under the name ‘newname’, add ‘-a newname’: ‘pintos -p file -a newname – -q’. The commands for copying files out of a VM are similar, but substitute ‘-g’ for ‘-p’.
Incidentally, these commands work by passing special commands extract and append on the kernel’s command line and copying to and from a special simulated “scratch” partition. If you’re very curious, you can look at the pintos script as well as ‘filesys/fsutil.c’ to learn the implementation details.
Here’s a summary of how to create a disk with a file system partition, format the file system, copy the echo program into the new disk, and then run echo, passing argument x. (Argument passing won’t work until you implemented it.) It assumes that you’ve already built the examples in ‘examples’ and that the current directory is ‘userprog/build’:

pintos-mkdisk filesys.dsk --filesys-size=2
pintos -f -q
pintos -p ../../examples/echo -a echo -- -q
pintos -q run apos;echo xapos;

The three final steps can actually be combined into a single command:

pintos-mkdisk filesys.dsk --filesys-size=2
pintos -p ../../examples/echo -a echo -- -f -q run apos;echo xapos;

If you don’t want to keep the file system disk around for later use or inspection, you can even combine all four steps into a single command. The –filesys-size=n option creates a temporary file system partition approximately n megabytes in size just for the duration of the pintos run. The Pintos automatic test suite makes extensive use of this syntax:

pintos --filesys-size=2 -p ../../examples/echo -a echo -- -f -q run apos;echo xapos;

You can delete a file from the Pintos file system using the rm file kernel action, e.g. pintos -q rm file. Also, ls lists the files in the file system and cat file prints a file’s contents to the display.

How User Programs Work

Pintos can run normal C programs, as long as they fit into memory and use only the system calls you implement. Notably, malloc() cannot be implemented because none of the system calls required for this project allow for memory allocation. Pintos also can’t run programs that use floating point operations, since the kernel doesn’t save and restore the processor’s floating-point unit when switching threads.
The ‘src/examples’ directory contains a few sample user programs. The ‘Makefile’ in this directory compiles the provided examples, and you can edit it to compile your own programs as well. Some of the example programs will only work once projects 3 or 4 have been implemented.
Pintos can load ELF executables with the loader provided for you in ‘userprog/process.c’. ELF is a file format used by Linux, Solaris, and many other operating systems for object files, shared libraries, and executables. You can actually use any compiler and linker that output 80x86 ELF executables to produce programs for Pintos. (We’ve provided compilers and linkers that should do just fine.)
You should realize immediately that, until you copy a test program to the simulated file system, Pintos will be unable to do useful work. You won’t be able to do interesting things until you copy a variety of programs to the file system. You might want to create a clean reference file system disk and copy that over whenever you trash your ‘filesys.dsk’ beyond a useful state, which may happen occasionally while debugging.

Virtual Memory Layout

Virtual memory in Pintos is divided into two regions: user virtual memory and kernel virtual memory. User virtual memory ranges from virtual address 0 up to PHYS_BASE, which is defined in ‘threads/vaddr.h’ and defaults to 0xc0000000 (3 GB). Kernel virtual memory occupies the rest of the virtual address space, from PHYS_BASE up to 4 GB.
User virtual memory is per-process. When the kernel switches from one process to another, it also switches user virtual address spaces by changing the processor’s page directory base register (see pagedir_activate() in ‘userprog/pagedir.c’). struct thread contains a pointer to a process’s page table.
Kernel virtual memory is global. It is always mapped the same way, regardless of what user process or kernel thread is running. In Pintos, kernel virtual memory is mapped one-to-one to physical memory, starting at PHYS_BASE. That is, virtual address PHYS_BASE accesses physical address 0, virtual address PHYS_BASE + 0x1234 accesses physical address 0x1234, and so on up to the size of the machine’s physical memory.
A user program can only access its own user virtual memory. An attempt to access kernel virtual memory causes a page fault, handled by page_fault() in ‘userprog/exception.c’, and the process will be terminated. Kernel threads can access both kernel virtual memory and, if a user process is running, the user virtual memory of the running process. However, even in the kernel, an attempt to access memory at an unmapped user virtual address will cause a page fault.

Typical Memory Layout

Conceptually, each process is free to lay out its own user virtual memory however it chooses. In practice, user virtual memory is laid out like this:
In this project, the user stack is fixed in size. Traditionally, the size of the uninitialized data segment can be adjusted with a system call, but you will not have to implement this.
The code segment in Pintos starts at user virtual address 0x08048000, approximately 128 MB from the bottom of the address space.
The linker sets the layout of a user program in memory, as directed by a “linker script” that tells it 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 ‘info ld’.
To view the layout of a particular executable, run objdump (80x86) or i386-elf-objdump (SPARC) with the ‘-p’ option.

Accessing User Memory

As part of a system call, the kernel must often access memory through pointers provided by a user program. The kernel must be very careful about doing so, because the user can pass a null pointer, a pointer to unmapped virtual memory, or a pointer to kernel virtual address space (above PHYS_BASE). All of these types of invalid pointers must be rejected without harm to the kernel or other running processes, by terminating the offending process and freeing its resources.
There are at least two reasonable ways to do this correctly. The first method is to verify the validity of a user-provided pointer, then dereference it. If you choose this route, you’ll want to look at the functions in ‘userprog/pagedir.c’ and in ‘threads/vaddr.h’. This is the simplest way to handle user memory access.
The second method is to check only that a user pointer points below PHYS_BASE, then dereference it. An invalid user pointer will cause a \page fault” that you can handle by modifying the code for page_fault() in ‘userprog/exception.c’. This technique is normally faster because it takes advantage of the processor’s MMU, so it tends to be used in real kernels (including Linux).
In either case, you need to make sure not to “leak” resources. For example, suppose that your system call has acquired a lock or allocated memory with malloc(). If you encounter an invalid user pointer afterward, you must still be sure to release the lock or free the page of memory. If you choose to verify user pointers before dereferencing them, this should be straightforward. It’s more difficult to handle if an invalid pointer causes a page fault, because there’s no way to return an error code from a memory access. Therefore, for those who want to try the latter technique, we’ll provide a little bit of helpful code:

/* Reads a byte at user virtual address UADDR.
   UADDR must be below PHYS_BASE. 
   Returns the byte value if successful, -1 if a segfault
   occurred. */

static int
get_user (const uint8_t *uaddr)
#123;
    int result;
    asm ("movl $1f, %0; movzbl %1, %0; 1:"
           : "=amp;a" (result) : "m" (*uaddr));
    return result; 
#125;

/* Writes BYTE to user address UDST.
   UDST must be below PHYS_BASE.
   Returns true if successful, false if a segfault occurred. */

static bool
put_user (uint8_t *udst, uint8_t byte)
#123;
    int error_code;
    asm ("movl $1f, %0; movb %b2, %1; 1:"
           : "=amp;a" (error_code), "=m" (*udst) : "q" (byte));
    return error_code != -1;
#125;

Suggested Order of Implementation

We suggest first implementing the following, which can happen in parallel:

Argument passing. Every user program will page fault immediately until argument passing is implemented.
For now, you may simply wish to change
*esp = PHYS_BASE;
to
*esp = PHYS_BASE - 12;
in setup_stack(). That will work for any test program that doesn’t examine its arguments, although its name will be printed as (null). Until you implement argument passing, you should only run programs without passing command-line arguments. Attempting to pass arguments to a program will include those arguments in the name of the program, which will probably fail.
User memory access. All system calls need to read user memory. Few system calls need to write to user memory.
System call infrastructure. Implement enough code to read the system call number from the user stack and dispatch to a handler based on it.
The exit system call. Every user program that finishes in the normal way calls exit. Even a program that returns from main() calls exit indirectly (see _start() in ‘lib/user/entry.c’).
The write system call for writing to fd 1, the system console. All of our test programs write to the console (the user process version of printf() is implemented this way), so they will all malfunction until write is available.
For now, change process_wait() to an infinite loop (one that waits forever). The provided implementation returns immediately, so Pintos will power off before any processes actually get to run. You will eventually need to provide a correct implementation.

After the above are implemented, user processes should work minimally. At the very least, they can write to the console and exit correctly. You can then refine your implementation so that some of the tests start to pass.