Pintos Projects: Project 2--User Programs (2025)

Now that you've worked with Pintos and are becoming familiar with itsinfrastructure and thread package, it's time to start working on theparts of the system that allow running user programs. The base codealready supports loading and running user programs, but no I/O or otherOS interaction is possible. In this project, you will enable programsto interact with the OS via system calls.

You will be working out of the userprog directory for thisassignment, but you will also be interacting with almost every otherpart of Pintos. We will describe the relevant parts below.

You can build project 2 on top of your project 1 submission or you canstart fresh (just return to 1. Introduction to download a fresh codebase). No code from project 1 is required for this assignment. You must work in a group of 2 to 4 people forthis project. Please see 3.3.6 General Requirements for moreinformation.

You might find it useful to go back and reread how to run the tests(see section 1.2.1 Testing).

3.1 Background

Up to now, all of the code you have run under Pintos has been part ofthe operating system kernel--even the test code from the lastassignment ran as part of the kernel and had full access to privilegedparts of the system. However, for user programs running on top of theoperating system access is restricted. This project deals with theconsequences.

In Pintos (and most other OSes), we allow more than one process to runat a time but, just as in your previous programming experience, userprograms are written under the illusion that they have the entiremachine. This means that when you load and run multiple processes at atime, you must manage memory, scheduling, and other state correctly tomaintain this illusion. In Pintos, each process has one thread(multithreaded processes are not supported).

In the previous project, we compiled our test code directly into yourkernel, so we had to require certain specific function interfaces withinthe kernel. From now on, we will test your operating system by runninguser programs. This gives you much greater freedom. You must make surethat the user program interface meets the specifications described here,but given that constraint you are free to restructure or rewrite kernelcode however you wish.

3.1.1 Source Files

The easiest way to get an overview of the programming you will bedoing is to simply go over each part you'll be working with. Inuserprog, you'll find a small number of files, but here iswhere 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.See section 4.1.2.3 Page Tables, for more information.

syscall.c

syscall.h

Whenever a user process wants to access some kernel functionality, itinvokes a system call. This is a skeleton system callhandler. Currently, it just prints a message and terminates the userprocess. In part 2 of this project you will add code to do everythingelse needed by system calls.

exception.c

exception.h

When a user process performs a privileged or prohibited operation, ittraps into the kernel as an "exception" or "fault."(2) These files handleexceptions. Currently all exceptions simply print a message andterminate the process. Some, but not all, solutions to project 2require modifying page_fault() in this file.

gdt.c

gdt.h

The 80x86 is a segmented architecture. The Global DescriptorTable (GDT) is a table that describes the segments in use. Thesefiles set up the GDT. You should not need to modify thesefiles for any of the projects. You can read the code ifyou're interested in how the GDT works.

tss.c

tss.h

The Task-State Segment (TSS) is used for 80x86 architecturaltask switching. Pintos uses the TSS only for switching stacks when auser process enters an interrupt handler, as does Linux. Youshould not need to modify these files for any of the projects.You can read the code if you're interested in how the TSSworks.

3.1.2 Using the File System

You will need to interface to the file system code for this project,because a) user programs are loaded from the file system and b) many ofthe 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 asimple but complete file system in the filesys directory. Youwill want to look over the filesys.h and file.h interfacesto understand how to use the file system and its many limitations.

There is no need to modify the file system code for this project, and sowe recommend that you do not. Working on the file system is likely todistract you from this project's focus.

Proper use of the file system routines now will make life much easierfor project 4, when you improve the file system implementation. Untilthen, you will have to tolerate the following limitations:

• No internal synchronization. Concurrent accesses will interfere withone another. You should use mutual exclusion and/orsynchronization to ensure that only one process at a time is executingfile system code.
• File size is fixed at creation time. The root directory is representedas 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 singlefile must occupy a contiguous range of sectors on disk. Externalfragmentation can therefore become a serious problem as a file system isused over time.
• No subdirectories.
• File names are limited to 14 characters.
• A system crash mid-operation may corrupt the disk in a way that cannotbe repaired automatically. There is also no file system repair tool.

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 andit may still be accessed by any threads that have it open, until thelast one closes it. See Removing an Open File, for more information.

You need to be able to create a simulated disk with a file systempartition. The pintos-mkdisk program provides thisfunctionality. From the userprog/build directory, executepintos-mkdisk filesys.dsk --filesys-size=2. This command createsa simulated disk named filesys.dsk that contains a 2 MBPintos file system partition. Then format the file system partition bypassing -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 -- isneeded because -p is for the pintos script, not forthe simulated kernel.) To copy it to the Pintos file system under thename newname, add -a newname: pintos-p file -a newname -- -q. The commands for copying filesout of the Pintos file system are similar, but substitute -gfor -p.

Incidentally, these commands work by passing special commandsextract and append on the kernel's command line andcopying to and from a special simulated "scratch" partition. Ifyou're very curious, you can look at the pintos script as wellas 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 newdisk, and then run echo, passing argument x. (Argumentpassing won't work until you implemented it.) It assumes that you'vealready built the examples in examples and that the currentdirectory is userprog/build:

pintos-mkdisk filesys.dsk --filesys-size=2pintos -f -qpintos -p ../../examples/echo -a echo -- -qpintos -q run 'echo x'

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

pintos-mkdisk filesys.dsk --filesys-size=2pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'

If you don't want to keep the file system disk around for later use orinspection, you can even combine all four steps into a single command.The --filesys-size=n option creates a temporary file systempartition approximately n megabytes in size just for the durationof the pintos run. The Pintos automatic test suite makesextensive use of this syntax:

pintos --filesys-size=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'

Note that make check uses the above command, and so any diskyou have previously created will be obliterated after runningmake check.

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

3.1.3 How User Programs Work

Pintos can run normal C programs, as long as they fit into memory and useonly the system calls you implement. Notably, malloc() cannot beimplemented because none of the system calls required for this projectallow for memory allocation. Pintos also can't run programs that usefloating point operations, since the kernel doesn't save and restore theprocessor'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 theexample programs will only work once projects 3 and/or 4 have beenimplemented.

Pintos can load ELF executables with the loader provided for youin 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 compilerand linker that output 80x86 ELF executables to produce programsfor Pintos. (We've provided compilers and linkers that should do justfine.)

You should realize immediately that, until you copy a test program tothe simulated file system, Pintos will be unable to do useful work. Youwon't be able to do interesting things until you copy a variety ofprograms to the file system. You might want to create a clean referencefile system disk and copy that over whenever you trash yourfilesys.dsk beyond a useful state, which may happen occasionallywhile debugging.

3.1.4 Virtual Memory Layout

Virtual memory in Pintos is divided into two regions: user virtualmemory and kernel virtual memory. User virtual memory ranges fromvirtual address 0 up to PHYS_BASE, which is defined inthreads/vaddr.h and defaults to 0xc0000000 (3 GB). Kernelvirtual memory occupies the rest of the virtual address space, fromPHYS_BASE up to 4 GB.

User virtual memory is per-process. When the kernel switches from oneprocess to another, it also switches user virtual address spaces bychanging the processor's page directory base register (seepagedir_activate() in userprog/pagedir.c). struct threadcontains 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, startingat PHYS_BASE. That is, virtual address PHYS_BASE accessesphysical address 0, virtual address PHYS_BASE + 0x1234accesses physical address 0x1234, and so on up to the size of themachine's physical memory.

A user program can only access its own user virtual memory. An attemptto access kernel virtual memory causes a page fault, handled bypage_fault() in userprog/exception.c, and the process willbe terminated. Kernel threads can access both kernel virtual memoryand, if a user process is running, the user virtual memory of therunning process. However, even in the kernel, an attempt to accessmemory at an unmapped user virtual address will cause a page fault.

3.1.4.1 Typical Memory Layout

Conceptually, each process is free to lay out its own user virtualmemory however it chooses. In practice, user virtual memory is laid outlike this:

 PHYS_BASE +----------------------------------+ | user stack | | | | | | | | V | | grows downward | | | | | | | | | | grows upward | | ^ | | | | | | | +----------------------------------+ | uninitialized data segment (BSS) | +----------------------------------+ | initialized data segment | +----------------------------------+ | code segment | 0x08048000 +----------------------------------+ | | | | | | | | | | 0 +----------------------------------+

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 variousprogram segments. You can learn more about linker scripts by readingthe "Scripts" chapter in the linker manual, accessible via infold.

The code segment in Pintos starts at user virtual address0x08048000, approximately 128 MB from the bottom of the addressspace. This value is specified in [ SysV-i386] and has no deepsignificance.

In this project, the user stack is fixed in size, but in project 3 itwill be allowed to grow. Traditionally, the size of the uninitializeddata segment can be adjusted with a system call, but you will not haveto implement this.

To view the layout of a particular executable, run objdump(80x86).

3.1.5 Accessing User Memory

As part of a system call, the kernel must often access memory throughpointers provided by a user program. The kernel must be very carefulabout doing so, because the user can pass a null pointer, a pointer tounmapped virtual memory, or a pointer to kernel virtual address space(above PHYS_BASE). All of these types of invalid pointers mustbe rejected without harm to the kernel or other running processes, byterminating the offending process and freeing its resources.

There are at least two reasonable ways to do this correctly. The firstmethod is to verify the validity of a user-provided pointer, thendereference it. If you choose this route, you'll want to look at thefunctions 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 belowPHYS_BASE, then dereference it. An invalid user pointer willcause a "page fault" that you can handle by modifying the code forpage_fault() in userprog/exception.c. This technique isnormally faster because it takes advantage of the processor's MMU, so ittends to be used in real kernels (including Linux). However, it is muchmore difficult to implement, so we recommend you use the first methodwhen implementing your project.

In either case, you need to make sure not to "leak" resources. Forexample, suppose that your system call has acquired a lock or allocatedmemory with malloc(). If you encounter an invalid user pointerafterward, you must still be sure to release the lock or free the pageof memory. If you choose to verify user pointers before dereferencingthem, this should be straightforward. It's more difficult to handle ifan invalid pointer causes a page fault, because there's no way to returnan error code from a memory access. Therefore, for those who want totry 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 intget_user (const uint8_t *uaddr){ int result; asm ("movl $1f, %0; movzbl %1, %0; 1:" : "=&a" (result) : "m" (*uaddr)); return result;} /* Writes BYTE to user address UDST. UDST must be below PHYS_BASE. Returns true if successful, false if a segfault occurred. */static boolput_user (uint8_t *udst, uint8_t byte){ int error_code; asm ("movl $1f, %0; movb %b2, %1; 1:" : "=&a" (error_code), "=m" (*udst) : "q" (byte)); return error_code != -1;}

Each of these functions assumes that the user address has already beenverified to be below PHYS_BASE. They also assume that you'vemodified page_fault() so that a page fault in the kernel merelysets eax to 0xffffffff and copies its former valueinto eip.

Again, the implementation of the second technique is complex, and wehighly recommend you use the first technique.

3.2 Suggested Order of Implementation

Before you begin this portion of the project, test your knowledge of thecode by answering the Code Reading Questions. Beingable to answer those questions before you begin coding will significantly helpyou.

We suggest first implementing the following, which can happen inparallel:

• For now, change process_wait() to an infinite loop (one that waitsforever). The provided implementation returns immediately, so Pintoswill power off before any processes actually get to run. You willeventually need to provide a correct implementation, as no tests willpass with this implementation. (With this suggested implementation,Pintos will hang forever, but at least you'll get to see output from thechild processes!)
• Argument passing (see section 3.3.3 Argument Passing).Every user program will page fault immediately until argument passing isimplemented.

  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'texamine its arguments, although its name will be printed as(null). (Note: This is a temporary fix, you must fully implementargument passing in this project.)

  Until you implement argument passing, you should only run programswithout passing command-line arguments. Attempting to pass arguments toa program will include those arguments in the name of the program, whichwill probably fail. (Recall that arguments are passed on the stack.)

• User memory access (see section 3.1.5 Accessing User Memory). All system callsneed to read user memory. Few system calls need to write to usermemory.
• System call infrastructure (see section 3.3.4 System Calls). Implement enoughcode to read the system call number from the user stack and dispatch toa handler based on it.
• The write system call for writing to fd 1, the system console.All of our test programs write to the console (the user process versionof printf() is implemented this way), so they will all malfunctionuntil write is available.
• The exit system call. Every user program that finishes in thenormal way calls exit. Even a program that returns frommain() calls exit indirectly (see _start() inlib/user/entry.c).

After the above are implemented, user processes should work minimally.At the very least, they can write to the console and exit correctly.Pintos, however, will not exit correctly until process_wait() isfully implemented, so you cannot rely on make check to test yourcode until that point. You can then refine your implementation so thatsome of the tests start to pass.

3.3 Requirements

3.3.1 Design Document

In addition to submitting your source code, each person is responsiblefor explaining and defending their project's design to us. For this project,you will have a code review where you explain your code to us. Your explanations, along with the quality of your code, will determine your grade.

We recommend you read thethe project 2 design document template before youstart working on the project.

3.3.2 Process Termination Messages

Whenever a user process terminates, because it called exitor for any other reason, print the process's name and exit code,formatted as if printed by printf ("%s: exit(%d)\n", ...);.The name printed should be the full name passed toprocess_execute(), omitting command-line arguments. Do not printthese messages when a kernel thread that is not a user processterminates, or when the halt system call is invoked. The messageis optional when a process fails to load.

Aside from this, don't print any other messages that Pintos as provideddoesn't already print. You may find extra messages useful duringdebugging, but they will confuse the grading scripts and thus lower yourscore.

3.3.3 Argument Passing

Currently, process_execute() does not support passing arguments tonew processes. Implement this functionality by extendingprocess_execute() so that instead of the argument string beingsimply the program file name, it is divided at spaces into the argumentsfor the program. The firstword is the program name, the second word is the first argument, and soon. That is, process_execute("grep foo bar") should rungrep passing two arguments foo and bar. Withina command line, multiple spaces are equivalent to a single space. Youcan impose a reasonable limit on the length of the command linearguments. For example, you could limit the arguments to those thatwill fit in a single page (4 kB). (There is an unrelated limit of 128bytes on command-line arguments that the pintos utility canpass to the kernel.)

Please note that at least two designs are possible: parsing arguments in setup_stack(), after simply separating the file name in process_execute(), or parsing all arguments in process_execute().

You can parse argument strings any way you like. If you're lost, lookat strtok_r(), prototyped in lib/string.h and implementedwith thorough comments in lib/string.c. You can find more aboutit by looking at the man page (run man strtok_r at the prompt).

Once you have parsed the arguments, you'll need to set up the stack sothat the arguments are passed. For information on exactly how to set upthe stack, See section 3.5.1 Program Startup Details.

This portion of your project is due at the Stack Check Deadline.

3.3.4 System Calls

Implement the system call handler in userprog/syscall.c. Theskeleton implementation we provide "handles" system calls byterminating the process. Instead, it will need to retrieve the systemcall number, then any system call arguments, and carry out appropriateactions.

Implement the following system calls. The prototypes listed are thoseseen by a user program that includes lib/user/syscall.h. (Thisheader, and all others in lib/user, are for use by user programsonly.) System call numbers for each system call are defined inlib/syscall-nr.h:

System Call: void halt (void)

Terminates Pintos by calling shutdown_power_off() (declared indevices/shutdown.h). This should be seldom used, because youlose some information about possible deadlock situations, etc.

System Call: void exit (int status)

Terminates the current user program, returning status to thekernel. If the process's parent waits for it (see below), thisis the status that will be returned. Conventionally, a status of0 indicates success and nonzero values indicate errors.

System Call: pid_t exec (const char *cmd_line)

Runs the executable whose name is given in cmd_line, passing anygiven arguments, and returns the new process's program id (pid). Mustreturn pid -1, which otherwise should not be a valid pid, if the programcannot load or run for any reason. Thus, the parent process cannotreturn from the exec until it knows whether the child processsuccessfully loaded its executable. You must use appropriatesynchronization to ensure this.

System Call: int wait (pid_t pid)

Waits for a child process pid and retrieves the child's exit status.

If pid is still alive, waits until it terminates. Then, returnsthe status that pid passed to exit. If pid did notcall exit(), but was terminated by the kernel (e.g. killed dueto an exception), wait(pid) must return -1. It is perfectlylegal for a parent process to wait for child processes that have alreadyterminated by the time the parent calls wait, but the kernel muststill allow the parent to retrieve its child's exit status or learn thatthe child was terminated by the kernel.

wait must fail and return -1 immediately if any of thefollowing conditions are true:

• pid does not refer to a direct child of the calling process.pid is a direct child of the calling process if and only if thecalling process received pid as a return value from a successfulcall to exec.

  Note that children are not inherited: if A spawns child Band B spawns child process C, then A cannot wait forC, even if B is dead. A call to wait(C) by processA must fail. Similarly, orphaned processes are not assigned to anew parent if their parent process exits before they do.

• The process that calls wait has already called wait onpid. That is, a process may wait for any given child at mostonce.

Processes may spawn any number of children, wait for them in any order,and may even exit without having waited for some or all of their children.Your design should consider all the ways in which waits can occur.All of a process's resources, including its struct thread, must befreed whether its parent ever waits for it or not, and regardless ofwhether the child exits before or after its parent.

You must ensure that Pintos does not terminate until the initialprocess exits. The supplied Pintos code tries to do this by callingprocess_wait() (in userprog/process.c) from main()(in threads/init.c). We suggest that you implementprocess_wait() according to the comment at the top of thefunction and then implement the wait system call in terms ofprocess_wait().

Implementing this system call requires considerably more work than anyof the rest.

System Call: bool create (const char *file, unsigned initial_size)

Creates a new file called file initially initial_size bytesin size. Returns true if successful, false otherwise. Creating a newfile does not open it: opening the new file is a separate operationwhich would require a open system call.

System Call: bool remove (const char *file)

Deletes the file called file. Returns true if successful, falseotherwise. A file may be removed regardless of whether it is open orclosed, and removing an open file does not close it. See Removing an Open File, for details.

System Call: int open (const char *file)

Opens the file called file. Returns a nonnegative integer handlecalled a "file descriptor" (fd) or -1 if the file could not beopened.

File descriptors numbered 0 and 1 are reserved for the console: fd 0(STDIN_FILENO) is standard input, fd 1 (STDOUT_FILENO) isstandard output. The open system call will never return eitherof these file descriptors, which are valid as system call arguments onlyas explicitly described below.

Each process has an independent set of file descriptors. Filedescriptors are not inherited by child processes.

When a single file is opened more than once, whether by a singleprocess or different processes, each open returns a new filedescriptor. Different file descriptors for a single file are closedindependently in separate calls to close and they do not sharea file position.

System Call: int filesize (int fd)

Returns the size, in bytes, of the file open as fd.

System Call: int read (int fd, void *buffer, unsigned size)

Reads size bytes from the file open as fd intobuffer. Returns the number of bytes actually read (0 at end offile), or -1 if the file could not be read (due to a condition otherthan end of file). fd 0 reads from the keyboard usinginput_getc().

System Call: int write (int fd, const void *buffer, unsigned size)

Writes size bytes from buffer to the open file fd.Returns the number of bytes actually written, which may be less thansize if some bytes could not be written.

Writing past end-of-file would normally extend the file, but file growthis not implemented by the basic file system. The expected behavior isto write as many bytes as possible up to end-of-file and return theactual number written, or 0 if no bytes could be written at all.

fd 1 writes to the console. Your code to write to the console shouldwrite all of buffer in one call to putbuf(), at least aslong as size is not bigger than a few hundred bytes. (It isreasonable to break up larger buffers.) Otherwise,lines of text output by different processes may end up interleaved onthe console, confusing both human readers and our grading scripts.

System Call: void seek (int fd, unsigned position)

Changes the next byte to be read or written in open file fd toposition, expressed in bytes from the beginning of the file.(Thus, a position of 0 is the file's start.)

A seek past the current end of a file is not an error. A later readobtains 0 bytes, indicating end of file. A later write extends thefile, filling any unwritten gap with zeros. (However, in Pintos, fileswill have a fixed length until project 4 is complete, so writes past end offile will return an error.) These semantics are implemented in thefile system and do not require any special effort in system callimplementation.

System Call: unsigned tell (int fd)

Returns the position of the next byte to be read or written in openfile fd, expressed in bytes from the beginning of the file.

System Call: void close (int fd)

Closes file descriptor fd. Exiting or terminating a process implicitly closes all its open filedescriptors, as if by calling this function for each one.

syscall.h defines other syscalls. Ignore them for now. You willimplement some of them in project 3 and the rest in project 4, so besure to design your system with extensibility in mind.

To implement syscalls, you need to provide ways to read and write datain user virtual address space. You need this ability before you caneven obtain the system call number, because the system call number is onthe user's stack in the user's virtual address space. This can be a bittricky: what if the user provides an invalid pointer, a pointer intokernel memory, or a block partially in one of those regions? You shouldhandle these cases by terminating the user process. We recommendwriting and testing this code before implementing any other system callfunctionality. See section 3.1.5 Accessing User Memory, for more information.

If a system call is passed an invalid argument, acceptable optionsinclude returning an error value (for those calls that return avalue), returning an undefined value, or terminating the process.

You must synchronize system calls so that any number of user processescan make them at once. In particular, it is not safe to call into thefile system code provided in the filesys directory from multiplethreads at once. Your system call implementation must treat the filesystem code as a critical section. Don't forget thatprocess_execute() also accesses files. For now, we recommendagainst modifying code in the filesys directory.

We have provided you a user-level function for each system call inlib/user/syscall.c. These provide a way for user processes toinvoke each system call from a C program. Each uses a little inlineassembly code to invoke the system call and (if appropriate) returns thesystem call's return value.

When you're done with this part, and forevermore, Pintos should bebulletproof. Nothing that a user program can do should ever cause theOS to crash, panic, fail an assertion, or otherwise malfunction. It isimportant to emphasize this point: our tests will try to break yoursystem calls in many, many ways. You need to think of all the cornercases and handle them. The sole way a user program should be able tocause the OS to halt is by invoking the halt system call.

See section 3.5.2 System Call Details, for details on how system calls work.

3.3.5 Denying Writes to Executables

Add code to deny writes to files in use as executables. Many OSes dothis because of the unpredictable results if a process tried to run codethat was in the midst of being changed on disk. This is especiallyimportant once virtual memory is implemented in project 3, but it can'thurt even now.

You can use file_deny_write() to prevent writes to an open file.Calling file_allow_write() on the file will re-enable them (unlessthe file is denied writes by another opener). Closing a file will alsore-enable writes. Thus, to deny writes to a process's executable, youmust keep it open as long as the process is still running.

3.3.6 General Requirements

You must work in two to four person teams on this project.

Failure to do so will result in a 0 for the project. You may work with the samepartner(s) you had for the last assignment or you may change partner(s). Onceyou have selected a partner, exchange first and last names, EIDs, and CS logins.Also, fill out the README.userprog distributed with the project andregister your group as a Userprog Group in Canvasby the date listed in the schedule.You must follow thepair programming guidelines set forth forthis class. Use the provided programming_log.userprog as your pair programming log.

Please see the Grading Criteriato understand how failure to follow the pair programming guidelines ORfill out the README.userprog will affect your grade.

You must complete this project.

If you do not turnin a completely working Project 2 (with the exception ofmulti-oom), you must get it working and demonstrate its correctness to a TAbefore you may move on to Projects 3 or 4.

You must follow the guidelines laid out in the C Style Guide or your will lose points.

This includes selecting reasonable names foryour files and variables.

This project will be graded on the UTCS public linux machines.

Although you are welcome to do testing and development on any platformyou like, we cannot assist you in setting up other environments, and youmust test and do final debugging on the UTCS public linux machines. Thestatement "It worked on my machine" will not be considered in thegrading process.

Your code must compile without any additions or adjustments or you will receive a 0 for the correctness portion.

You may not look at the written work of any student outside of your group.

This includes, for example, looking at another student'sscreen to help them debug, looking at another student's print-out,working with another student to sketch a high-level design on awhite-board. See the syllabus for additional details.

3.3.7 Turnin Instructions

For the Stack Check Deadline: At the stack check due date, youmust meet with a member of the course staff to show that argumentpassing is working (i.e., you have implemented the stack). Passing thestack check is required to earn a Level 3 or higher on your test cases score. Watch the discussion board for information regarding how to make an appointment.

For the rest of the project:

After you finish your code, please use make turnin_user (in thesrc directory) to create a compressed tarball for submission. Thefilename format will be userprog_turnin.tar.gz. Then, upload the.tar.gz file to the Project 2 Test Cases assignment inCanvas. Only one member of the pair should perform the upload. Make sure youhave included the necessary information in the README.userprog.

For this project,you will have a design interview, and that interview, along with a review ofyour code, will determine your grade.Your group must still submit a design document through Canvas to the Project 2Design and Documentation assignment, so that we can organize the interviews properly. Additionally, we recommend you read thethe project 2 design document template before youstart working on the project.

3.4 FAQ

Do I have to work with a partner or a group?

Yes. You must work with least one person but no more than four people.Register your group as a Userprog Group inCanvas by the date listed in the schedule.

How do I submit my work? And what is this stack check?

See See section 3.3.7 Turnin Instructions.

How much code will I need to write?

Here's a summary of our reference solution, produced by thediffstat program. The final row gives total lines insertedand deleted; a changed line counts as both an insertion and a deletion.

The reference solution represents just one possible solution, includes a greatmany comments, and includes all code for both this project and the previousprojects. Many other solutions are also possible and many of those differgreatly from the reference solution. Some excellent solutions may not modifyall the files modified by the reference solution, and some may modify files notmodified by the reference solution.

threads/thread.c | 13 threads/thread.h | 26 + userprog/exception.c | 8 userprog/process.c | 247 ++++++++++++++-- userprog/syscall.c | 468 ++++++++++++++++++++++++++++++- userprog/syscall.h | 1 6 files changed, 725 insertions(+), 38 deletions(-)

The kernel always panics when I run pintos -p file -- -q.

Did you format the file system (with pintos -f)?

Is your file name too long? The file system limits file names to 14characters. A command like pintos -p ../../examples/echo -- -qwill exceed the limit. Use pintos -p ../../examples/echo -a echo-- -q to put the file under the name echo instead.

Is the file system full?

Does the file system already contain 16 files? The base Pintos filesystem has a 16-file limit.

The file system may be so fragmented that there's not enough contiguousspace for your file.

When I run pintos -p ../file --, file isn't copied.

Files are written under the name you refer to them, by default, so inthis case the file copied in would be named ../file. Youprobably want to run pintos -p ../file -a file -- instead.

You can list the files in your file system with pintos -q ls.

All my user programs die with page faults.

This will happen if you haven't implemented argument passing(or haven't done so correctly). The basic C library for user programs triesto read argc and argv off the stack. If the stackisn't properly set up, this causes a page fault.

All my user programs die with system call!

You'll have to implement system calls before you see anything else.Every reasonable program tries to make at least one system call(exit()) and most programs make more than that. Notably,printf() invokes the write system call. The default systemcall handler just prints system call! and terminates the program.Until then, you can use hex_dump() to convince yourself thatargument passing is implemented correctly (see section 3.5.1 Program Startup Details).

How can I disassemble user programs?

The objdump (80x86) or i386-elf-objdump(SPARC) utility can disassemble entire userprograms or object files. Invoke it as objdump -dfile. You can use GDB'sdisassemble command to disassemble individual functions(see section E.5 GDB).

Why do many C include files not work in Pintos programs?

Can I use libfoo in my Pintos programs?

The C library we provide is very limited. It does not include many ofthe features that are expected of a real operating system's C library.The C library must be built specifically for the operating system (andarchitecture), since it must make system calls for I/O and memoryallocation. (Not all functions do, of course, but usually the libraryis compiled as a unit.)

The chances are good that the library you want uses parts of the C librarythat Pintos doesn't implement. It will probably take at least someporting effort to make it work under Pintos. Notably, the Pintosuser program C library does not have a malloc() implementation.

How do I compile new user programs?

Modify src/examples/Makefile, then run make.

Can I run user programs under a debugger?

Yes, with some limitations. See section E.5 GDB.

What's the difference between tid_t and pid_t?

A tid_t identifies a kernel thread, which may have a userprocess running in it (if created with process_execute()) or not(if created with thread_create()). It is a data type used onlyin the kernel.

A pid_t identifies a user process. It is used by userprocesses and the kernel in the exec and wait systemcalls.

You can choose whatever suitable types you like for tid_t andpid_t. By default, they're both int. You can make thema one-to-one mapping, so that the same values in both identify thesame process, or you can use a more complex mapping. It's up to you.

3.4.1 Argument Passing FAQ

Isn't the top of stack in kernel virtual memory?

The top of stack is at PHYS_BASE, typically 0xc0000000, whichis also where kernel virtual memory starts.But before the processor pushes data on the stack, it decrements the stackpointer. Thus, the first (4-byte) value pushed on the stackwill be at address 0xbffffffc.

Is PHYS_BASE fixed?

No. You should be able to support PHYS_BASE values that areany multiple of 0x10000000 from 0x80000000 to 0xf0000000,simply via recompilation.

3.4.2 System Calls FAQ

Can I just cast a struct file * to get a file descriptor?

Can I just cast a struct thread * to a pid_t?

You will have to make these design decisions yourself.Most operating systems do distinguish between filedescriptors (or pids) and the addresses of their kernel datastructures. You might want to give some thought as to why they do sobefore committing yourself.

Can I set a maximum number of open files per process?

It is better not to set an arbitrary limit, but you may impose a limitof 128 open files per process, if absolutely necessary.

What happens when an open file is removed?

You should implement the standard Unix semantics for files. That is, whena file is removed any process which has a file descriptor for that filemay continue to use that descriptor. This means thatthey can read and write from the file. The file will not have a name,and no other processes will be able to open it, but it will continueto exist until all file descriptors referring to the file are closedor the machine shuts down.

How can I run user programs that need more than 4 kB stack space?

You may modify the stack setup code to allocate more than one page ofstack space for each process. In the next project, you will implement abetter solution.

What should happen if an exec fails midway through loading?

exec should return -1 if the child process fails to load forany reason. This includes the case where the load fails part of theway through the process (e.g. where it runs out of memory in themulti-oom test). Therefore, the parent process cannot returnfrom the exec system call until it is established whether theload was successful or not. The child must communicate thisinformation to its parent using appropriate synchronization, such as asemaphore (see section A.3.2 Semaphores), to ensure that the information iscommunicated without race conditions.

3.5 80x86 Calling Convention

This section summarizes important points of the convention used fornormal function calls on 32-bit 80x86 implementations of Unix.Some details are omitted for brevity. If you do want all the details,refer to [ SysV-i386].

The calling convention works like this:

1. The caller pushes each of the function's arguments on the stack one byone, normally using the PUSH assembly language instruction.Arguments are pushed in right-to-left order.

   The stack grows downward: each push decrements the stack pointer, thenstores into the location it now points to, like the C expression*--sp = value.

2. The caller pushes the address of its next instruction (the returnaddress) on the stack and jumps to the first instruction of the callee.A single 80x86 instruction, CALL, does both.
3. The callee executes. When it takes control, the stack pointer points tothe return address, the first argument is just above it, the secondargument is just above the first argument, and so on.
4. If the callee has a return value, it stores it into register EAX.
5. The callee returns by popping the return address from the stack andjumping to the location it specifies, using the 80x86 RETinstruction.
6. The caller pops the arguments off the stack.

Consider a function f() that takes three int arguments.This diagram shows a sample stack frame as seen by the callee at thebeginning of step 3 above, supposing that f() is invoked asf(1, 2, 3). The initial stack address is arbitrary:

 +----------------+ 0xbffffe7c | 3 | 0xbffffe78 | 2 | 0xbffffe74 | 1 |stack pointer --> 0xbffffe70 | return address | +----------------+

3.5.1 Program Startup Details

The Pintos C library for user programs designates _start(), inlib/user/entry.c, as the entry point for user programs. Thisfunction is a wrapper around main() that calls exit() ifmain() returns:

void_start (int argc, char *argv[]) { exit (main (argc, argv));}

The kernel must put the arguments for the initial function on the stackbefore it allows the user program to begin executing. The arguments arepassed in the same way as the normal calling convention (see section 3.5 80x86 Calling Convention).

Consider how to handle arguments for the following example command:/bin/ls -l foo bar.First, break the command into words: /bin/ls,-l, foo, bar. Place the words at the top of thestack. Order doesn't matter, because they will be referenced throughpointers.

Then, push the address of each string plus a null pointer sentinel, onthe stack, in right-to-left order. These are the elements ofargv. The null pointer sentinel ensures that argv[argc]is a null pointer, as required by the C standard. The order ensuresthat argv[0] is at the lowest virtual address. Word-alignedaccesses are faster than unaligned accesses, so for best performanceround the stack pointer down to a multiple of 4 before the first push.

Then, push argv (the address of argv[0]) and argc,in that order. Finally, push a fake "return address": although theentry function will never return, its stack frame must have the samestructure as any other.

The table below shows the state of the stack and the relevant registersright before the beginning of the user program, assumingPHYS_BASE is 0xc0000000:

In this example, the stack pointer would be initialized to0xbfffffcc.

As shown above, your code should start the stack at the very top ofthe user virtual address space, in the page just below virtual addressPHYS_BASE (defined in threads/vaddr.h).

You may find the non-standard hex_dump() function, declared in<stdio.h>, useful for debugging your argument passing code.Here's what it would show in the above example:

bfffffc0 00 00 00 00 | ....|bfffffd0 04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|bfffffe0 f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|bffffff0 6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|

3.5.2 System Call Details

The first project already dealt with one way that the operating systemcan regain control from a user program: interrupts from timers and I/Odevices. These are "external" interrupts, because they are causedby entities outside the CPU (see section A.4.3 External Interrupt Handling).

The operating system also deals with software exceptions, which areevents that occur in program code (see section A.4.2 Internal Interrupt Handling). These can be errors such as a page fault or division byzero. Exceptions are also the means by which a user programcan request services ("system calls") from the operating system.

In the 80x86 architecture, the int instruction is themost commonly used means for invoking system calls. This instructionis handled in the same way as other software exceptions. In Pintos,user programs invoke int $0x30 to make a system call. Thesystem call number and any additional arguments are expected to bepushed on the stack in the normal fashion before invoking theinterrupt (see section 3.5 80x86 Calling Convention).

Thus, when the system call handler syscall_handler() gets control,the system call number is in the 32-bit word at the caller's stackpointer, the first argument is in the 32-bit word at the next higheraddress, and so on. The caller's stack pointer is accessible tosyscall_handler() as the esp member of thestruct intr_frame passed to it. (struct intr_frame is on the kernelstack.)

The 80x86 convention for function return values is to place themin the EAX register. System calls that return a value can doso by modifying the eax member of struct intr_frame.

You should try to avoid writing large amounts of repetitive code forimplementing system calls. Each system call argument, whether aninteger or a pointer, takes up 4 bytes on the stack. You should be ableto take advantage of this to avoid writing much near-identical code forretrieving each system call's arguments from the stack.