1 @node Project 2--User Programs, Project 3--Virtual Memory, Project 1--Threads, Top
2 @chapter Project 2: User Programs
4 Now that you've worked with Pintos and are becoming familiar with its
5 infrastructure and thread package, it's time to start working on the
6 parts of the system that allow running user programs.
7 The base code already supports loading and
8 running user programs, but no I/O or interactivity
9 is possible. In this project, you will enable programs to interact with
10 the OS via system calls.
12 You will be working out of the @file{userprog} directory for this
13 assignment. However, you will also be interacting with almost every
14 other part of the code for this assignment. We will describe the
17 You can build project 2 on top of your project 1 submission or you can
18 start with a fresh copy. No code from project 1 is required for this
19 assignment. The ``alarm clock'' functionality may be useful in
20 projects 3 and 4, but it is not strictly required.
23 * Project 2 Background::
24 * Project 2 Requirements::
26 * 80x86 Calling Convention::
29 @node Project 2 Background
32 Up to now, all of the code you have run under Pintos has been part
33 of the operating system kernel. This means, for example, that all the
34 test code from the last assignment ran as part of the kernel, with
35 full access to privileged parts of the system. Once we start running
36 user programs on top of the operating system, this is no longer true.
37 This project deals with consequences of the change.
39 We allow more than one process to run at a time. Each process has one
40 thread (multithreaded processes are not supported). User programs are
41 written under the illusion that they have the entire machine. This
42 means that when you load and run multiple processes at a time, you must
43 manage memory, scheduling, and other state correctly to maintain this
46 In the previous project, we compiled our test code directly into your
47 kernel, so we had to require certain specific function interfaces within
48 the kernel. From now on, we will test your operating system by running
49 user programs. This gives you much greater freedom. You must make sure
50 that the user program interface meets the specifications described here,
51 but given that constraint you are free to restructure or rewrite kernel
52 code however you wish.
55 * Project 2 Source Files::
56 * Using the File System::
57 * How User Programs Work::
58 * Virtual Memory Layout::
59 * Accessing User Memory::
62 @node Project 2 Source Files
63 @subsection Source Files
65 The easiest way to get an overview of the programming you will be
66 doing is to simply go over each part you'll be working with. In
67 @file{userprog}, you'll find a small number of files, but here is
68 where the bulk of your work will be:
73 Loads ELF binaries and starts processes.
77 A simple manager for 80@var{x}86 page directories and page tables.
78 Although you probably won't want to modify this code for this project,
79 you may want to call some of its functions.
83 Whenever a user process wants to access some kernel functionality, it
84 invokes a system call. This is a skeleton system call
85 handler. Currently, it just prints a message and terminates the user
86 process. In part 2 of this project you will add code to do everything
87 else needed by system calls.
91 When a user process performs a privileged or prohibited operation, it
92 traps into the kernel as an ``exception'' or ``fault.''@footnote{We
93 will treat these terms as synonymous. There is no standard
94 distinction between them, although Intel processor manuals define
95 them slightly differently on 80@var{x}86.} These files handle
96 exceptions. Currently all exceptions simply print a message and
97 terminate the process. Some, but not all, solutions to project 2
98 require modifying @func{page_fault} in this file.
102 The 80@var{x}86 is a segmented architecture. The Global Descriptor
103 Table (GDT) is a table that describes the segments in use. These
104 files set up the GDT. @strong{You should not need to modify these
105 files for any of the projects.} You can read the code if
106 you're interested in how the GDT works.
110 The Task-State Segment (TSS) is used for 80@var{x}86 architectural
111 task switching. Pintos uses the TSS only for switching stacks when a
112 user process enters an interrupt handler, as does Linux. @strong{You
113 should not need to modify these files for any of the projects.}
114 You can read the code if you're interested in how the TSS
118 @node Using the File System
119 @subsection Using the File System
121 You will need to use some file system code for this project. First,
122 user programs are loaded from the file system. Second, many of the
123 system calls you must implement deal with the file system. However,
124 the focus of this project is not on the file system code, so we have
125 provided a simple file system in the @file{filesys} directory. You
126 will want to look over the @file{filesys.h} and @file{file.h}
127 interfaces to understand how to use the file system, and especially
128 its many limitations. @strong{You should not modify the file system
129 code for this project.} Proper use of the file system routines now
130 will make life much easier for project 4, when you improve the file
131 system implementation. Until then, you will have to put up with the
132 following limitations:
136 No synchronization. Concurrent accesses will interfere with one
137 another. You should use a global lock to ensure that only one process at a
138 time is executing file system code.
141 File size is fixed at creation time. The root directory is
142 represented as a file, so the number of files that may be created is also
146 File data is allocated as a single extent, that is, data in a single
147 file must occupy a contiguous range of sectors on disk. External
148 fragmentation can therefore become a serious problem as a file system is
155 File names are limited to 14 characters.
158 A system crash mid-operation may corrupt the disk in a way
159 that cannot be repaired automatically. There is no file system repair
163 One important feature is included:
167 Unix-like semantics for @func{filesys_remove} are implemented.
168 That is, if a file is open when it is removed, its blocks
169 are not deallocated and it may still be accessed by any
170 threads that have it open until the last one closes it. @xref{Removing
171 an Open File}, for more information.
174 You need to be able to create simulated disks. The
175 @command{pintos-mkdisk} program provides this functionality. From the
176 @file{userprog/build} directory, execute @code{pintos-mkdisk fs.dsk 2}.
177 This command creates a 2 MB simulated disk named @file{fs.dsk}. Then
178 format the disk by passing @option{-f -q} on the kernel's command
179 line: @code{pintos -f -q}. The @option{-f} option causes the disk to be
180 formatted, and @option{-q} causes Pintos to exit as soon as the format
183 You'll need a way to copy files in and out of the simulated file system.
184 The @code{pintos} @option{-p} (``put'') and @option{-g} (``get'')
185 options do this. To copy @file{@var{file}} into the
186 Pintos file system, use the command @file{pintos -p @var{file} -- -q}.
187 (The @samp{--} is needed because @option{-p} is for the @command{pintos}
188 script, not for the simulated kernel.) To copy it to the Pintos file
189 system under the name @file{@var{newname}}, add @option{-a
190 @var{newname}}: @file{pintos -p @var{file} -a @var{newname} -- -q}. The
191 commands for copying files out of a VM are similar, but substitute
192 @option{-g} for @option{-p}.
194 Incidentally, these commands work by passing special commands
195 @command{put} and @command{get} on the kernel's command line and copying
196 to and from a special simulated ``scratch'' disk. If you're very
197 curious, you can look at the @command{pintos} program as well as
198 @file{filesys/fsutil.c} to learn the implementation details.
200 Here's a summary of how to create and format a disk, copy the
201 @command{echo} program into the new disk, and then run @command{echo},
202 passing argument @code{x}. (Argument passing won't work until
203 you've implemented it.) It assumes
204 that you've already built the
205 examples in @file{examples} and that the current directory is
206 @file{userprog/build}:
209 pintos-mkdisk fs.dsk 2
211 pintos -p ../../examples/echo -a echo -- -q
212 pintos -q run 'echo x'
215 The three final steps can actually be combined into a single command:
218 pintos-mkdisk fs.dsk 2
219 pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'
222 If you don't want to keep the file system disk around for later use or
223 inspection, you can even combine all four steps into a single command.
224 The @code{--fs-disk=2} option creates a temporary disk just for the
225 duration of the @command{pintos} run. The Pintos automatic test suite
226 makes extensive use of this syntax:
229 pintos --fs-disk=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'
232 You can delete a file from the Pintos file system using the @code{rm
233 @var{file}} kernel action, e.g.@: @code{pintos -q rm @var{file}}. Also,
234 @command{ls} lists the files in the file system and @code{cat
235 @var{file}} prints a file's contents to the display.
237 @node How User Programs Work
238 @subsection How User Programs Work
240 Pintos can run normal C programs. In fact, Pintos can run any program
241 you want, as long as it's compiled into the proper file format and uses
242 only the system calls you implement. Notably, @func{malloc} cannot be
243 implemented because none of the system calls required for this project
244 allow for memory allocation. Pintos also can't run programs that use
245 floating point operations, since the kernel doesn't save and restore the
246 processor's floating-point unit when switching threads.
248 The @file{src/examples} directory contains a few sample user
249 programs. The @file{Makefile} in this directory
250 compiles the provided examples, and you can edit it
251 compile your own programs as well.
253 Pintos loads @dfn{ELF} executables. ELF is a file format used by Linux,
254 Solaris, and many other operating systems for object files,
255 shared libraries, and executables. You can actually use any compiler
256 and linker that output 80@var{x}86 ELF executables to produce programs
257 for Pintos. (We've provided compilers and linkers that should do just
260 You should realize immediately that, until you copy a
261 test program to the emulated disk, Pintos will be unable to do
262 useful work. You won't be able to do
263 interesting things until you copy a variety of programs to the disk.
264 You might want to create a clean reference disk and copy that
265 over whenever you trash your @file{fs.dsk} beyond a useful state,
266 which may happen occasionally while debugging.
268 @node Virtual Memory Layout
269 @subsection Virtual Memory Layout
271 Virtual memory in Pintos is divided into two regions: user virtual
272 memory and kernel virtual memory. User virtual memory ranges from
273 virtual address 0 up to @code{PHYS_BASE}, which is defined in
274 @file{threads/mmu.h} and defaults to @t{0xc0000000} (3 GB). Kernel
275 virtual memory occupies the rest of the virtual address space, from
276 @code{PHYS_BASE} up to 4 GB.
278 User virtual memory is per-process.
279 When the kernel switches from one process to another, it
280 also switches user virtual address spaces by changing the processor's
281 page directory base register (see @func{pagedir_activate} in
282 @file{userprog/pagedir.c}). @struct{thread} contains a pointer to a
283 process's page directory.
285 Kernel virtual memory is global. It is always mapped the same way,
286 regardless of what user process or kernel thread is running. In
287 Pintos, kernel virtual memory is mapped one-to-one to physical
288 memory, starting at @code{PHYS_BASE}. That is, virtual address
289 @code{PHYS_ADDR} accesses physical
290 address 0, virtual address @code{PHYS_ADDR} + @t{0x1234} access
291 physical address @t{0x1234}, and so on up to the size of the machine's
294 A user program can only access its own user virtual memory. An attempt to
295 access kernel virtual memory causes a page fault, handled by
296 @func{page_fault} in @file{userprog/exception.c}, and the process
297 will be terminated. Kernel threads can access both kernel virtual
298 memory and, if a user process is running, the user virtual memory of
299 the running process. However, even in the kernel, an attempt to
300 access memory at a user virtual address that doesn't have a page
301 mapped into it will cause a page fault.
303 You must handle memory fragmentation gracefully, that is, a process that
304 needs @var{N} pages of user virtual memory must not require those pages
305 to be contiguous in kernel virtual memory.
308 * Typical Memory Layout::
311 @node Typical Memory Layout
312 @subsubsection Typical Memory Layout
314 Conceptually, each process is
315 free to lay out its own user virtual memory however it
316 chooses. In practice, user virtual memory is laid out like this:
323 PHYS_BASE +----------------------------------+
337 +----------------------------------+
338 | uninitialized data segment (BSS) |
339 +----------------------------------+
340 | initialized data segment |
341 +----------------------------------+
343 0x08048000 +----------------------------------+
349 0 +----------------------------------+
356 In this project, the user stack is fixed in size, but in project 3 it
357 will be allowed to grow. Traditionally, the size of the uninitialized
358 data segment can be adjusted with a system call, but you will not have
361 The code segment in Pintos starts at user virtual address
362 @t{0x08084000}, approximately 128 MB from the bottom of the address
363 space. This value is specified in @bibref{SysV-i386} and has no deep
366 The linker sets the layout of a user program in memory, as directed by a
367 ``linker script'' that tells it the names and locations of the various
368 program segments. You can learn more about linker scripts by reading
369 the ``Scripts'' chapter in the linker manual, accessible via @samp{info
372 To view the layout of a particular executable, run @command{objdump}
373 (80@var{x}86) or @command{i386-elf-objdump} (SPARC) with the @option{-p}
376 @node Accessing User Memory
377 @subsection Accessing User Memory
380 call, the kernel must often access memory through pointers provided by a user
381 program. The kernel must be very careful about doing so, because
382 the user can pass a null pointer, a pointer to
383 unmapped virtual memory, or a pointer to kernel virtual address space
384 (above @code{PHYS_BASE}). All of these types of invalid pointers must
385 be rejected without harm to the kernel or other running processes, by
386 terminating the offending process and freeing its resources.
388 There are at least two reasonable ways to do this correctly. The
389 first method is to verify
390 the validity of a user-provided pointer, then dereference it. If you
391 choose this route, you'll want to look at the functions in
392 @file{userprog/pagedir.c} and in @file{threads/mmu.h}. This is the
393 simplest way to handle user memory access.
395 The second method is to check only that a user
396 pointer points below @code{PHYS_BASE}, then dereference it.
397 An invalid user pointer will cause a ``page fault'' that you can
398 handle by modifying the code for @func{page_fault} in
399 @file{userprog/exception.cc}. This technique is normally faster
400 because it takes advantage of the processor's MMU, so it tends to be
401 used in real kernels (including Linux).
403 In either case, you need to make sure not to ``leak'' resources. For
404 example, suppose that your system call has acquired a lock or
405 allocated a page of memory. If you encounter an invalid user pointer
406 afterward, you must still be sure to release the lock or free the page
407 of memory. If you choose to verify user pointers before dereferencing
408 them, this should be straightforward. It's more difficult to handle
409 if an invalid pointer causes a page fault,
410 because there's no way to return an error code from a memory access.
411 Therefore, for those who want to try the latter technique, we'll
412 provide a little bit of helpful code:
415 /* Tries to copy a byte from user address USRC to kernel address KDST.
416 Returns true if successful, false if USRC is invalid. */
417 static inline bool get_user (uint8_t *kdst, const uint8_t *usrc) {
419 asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
420 : "=m" (*kdst), "=&a" (eax) : "m" (*usrc));
424 /* Tries to write BYTE to user address UDST.
425 Returns true if successful, false if UDST is invalid. */
426 static inline bool put_user (uint8_t *udst, uint8_t byte) {
428 asm ("movl $1f, %%eax; movb %b2, %0; 1:"
429 : "=m" (*udst), "=&a" (eax) : "r" (byte));
434 Each of these functions assumes that the user address has already been
435 verified to be below @code{PHYS_BASE}. They also assume that you've
436 modified @func{page_fault} so that a page fault in the kernel causes
437 @code{eax} to be set to 0 and its former value copied into @code{eip}.
439 @node Project 2 Requirements
440 @section Requirements
443 * Project 2 Design Document::
444 * Process Termination Messages::
447 * Denying Writes to Executables::
450 @node Project 2 Design Document
451 @subsection Design Document
453 Before you turn in your project, you must copy @uref{userprog.tmpl, ,
454 the project 2 design document template} into your source tree under the
455 name @file{pintos/src/userprog/DESIGNDOC} and fill it in. We recommend
456 that you read the design document template before you start working on
457 the project. @xref{Project Documentation}, for a sample design document
458 that goes along with a fictitious project.
460 @node Process Termination Messages
461 @subsection Process Termination Messages
463 Whenever a user process terminates, because it called @code{exit}
464 or for any other reason, print the process's name
465 and exit code, formatted as if printed by @code{printf ("%s:
466 exit(%d)\n", @dots{});}. The name printed should be the full name
467 passed to @func{process_execute}, omitting command-line arguments.
468 Do not print these messages when a kernel thread that is not a user
469 process terminates, or
470 when the @code{halt} system call is invoked. The message is optional
471 when a process fails to load.
473 Aside from this, don't print any other
474 messages that Pintos as provided doesn't already print. You may find
475 extra messages useful during debugging, but they will confuse the
476 grading scripts and thus lower your score.
478 @node Argument Passing
479 @subsection Argument Passing
481 Currently, @func{process_execute} does not support passing arguments to
482 new processes. Implement this functionality, by extending
483 @func{process_execute} so that instead of simply taking a program file
484 name as its argument, it divides it into words at spaces. The first
485 word is the program name, the second word is the first argument, and so
486 on. That is, @code{process_execute("grep foo bar")} should run
487 @command{grep} passing two arguments @code{foo} and @code{bar}.
489 Within a command line, multiple spaces are equivalent to a single space,
490 so that @code{process_execute("grep foo bar")} is equivalent to our
491 original example. You can impose a reasonable limit on the length of
492 the command line arguments. For example, you could limit the arguments
493 to those that will fit in a single page (4 kB).
495 You can parse argument strings any way you like. If you're lost,
496 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
497 implemented with thorough comments in @file{lib/string.c}. You can
498 find more about it by looking at the man page (run @code{man strtok_r}
501 @xref{Program Startup Details}, for information on exactly how you
502 need to set up the stack.
505 @subsection System Calls
507 Implement the system call handler in @file{userprog/syscall.c}. The
508 skeleton implementation we provide ``handles'' system calls by
509 terminating the process. It will need to retrieve the system call
510 number, then any system call arguments, and carry appropriate actions.
512 Implement the following system calls. The prototypes listed are those
513 seen by a user program that includes @file{lib/user/syscall.h}. System
514 call numbers for each system call are defined in
515 @file{lib/syscall-nr.h}:
517 @deftypefn {System Call} void halt (void)
518 Terminates Pintos by calling @func{power_off} (declared in
519 @file{threads/init.h}). Note that this should be seldom used, since
520 then you lose some information about possible deadlock situations,
524 @deftypefn {System Call} void exit (int @var{status})
525 Terminates the current user program, returning @var{status} to the
526 kernel. If the process's parent @code{wait}s for it (see below), this
528 that will be returned. Conventionally, a @var{status} of 0 indicates
529 success and nonzero values indicate errors.
532 @deftypefn {System Call} pid_t exec (const char *@var{cmd_line})
533 Runs the executable whose name is given in @var{cmd_line}, passing any
534 given arguments, and returns the new process's program id (pid). Must
535 return pid -1, which otherwise should not be a valid pid, if
536 the program cannot load or run for any reason.
539 @deftypefn {System Call} int wait (pid_t @var{pid})
540 Waits for process @var{pid} to die and returns the status it passed to
541 @code{exit}. Returns -1 if @var{pid}
542 was terminated by the kernel (i.e.@: killed due to an exception). If
543 @var{pid} is invalid or if it was not a child of the
544 calling thread, or if @code{wait} has already been successfully
545 called for the given @var{pid}, returns -1 immediately, without
548 You must ensure that Pintos does not terminate until the initial
549 process exits. The supplied Pintos code tries to do this by calling
550 @func{process_wait} (in @file{userprog/process.c}) from @func{main}
551 (in @file{threads/init.c}). We suggest that you implement
552 @func{process_wait} according to the comment at the top of the
553 function and then implement the @code{wait} system call in terms of
556 All of a process's resources, including its @struct{thread}, must be
557 freed whether its parent ever waits for it or not, and regardless of
558 whether the child exits before or after its parent.
560 Children are not inherited: if @var{A} has child @var{B} and
561 @var{B} has child @var{C}, then @code{wait(C)} always returns immediately
562 when called from @var{A}, even if @var{B} is dead.
564 Consider all the ways a wait can occur: nested waits (@var{A} waits
565 for @var{B}, then @var{B} waits for @var{C}), multiple waits (@var{A}
566 waits for @var{B}, then @var{A} waits for @var{C}), and so on.
569 @deftypefn {System Call} bool create (const char *@var{file}, unsigned @var{initial_size})
570 Creates a new file called @var{file} initially @var{initial_size} bytes
571 in size. Returns true if successful, false otherwise.
573 Consider implementing this function in terms of @func{filesys_create}.
576 @deftypefn {System Call} bool remove (const char *@var{file})
577 Deletes the file called @var{file}. Returns true if successful, false
580 Consider implementing this function in terms of @func{filesys_remove}.
583 @deftypefn {System Call} int open (const char *@var{file})
584 Opens the file called @var{file}. Returns a nonnegative integer handle
585 called a ``file descriptor'' (fd), or -1 if the file could not be
586 opened. All open files associated with a process should be closed
587 when the process exits or is terminated.
589 File descriptors numbered 0 and 1 are reserved for the console: fd 0
590 is standard input (@code{stdin}), fd 1 is standard output
591 (@code{stdout}). These special file descriptors are valid as system
592 call arguments only as explicitly described below.
594 Consider implementing this function in terms of @func{filesys_open}.
597 @deftypefn {System Call} int filesize (int @var{fd})
598 Returns the size, in bytes, of the file open as @var{fd}.
600 Consider implementing this function in terms of @func{file_length}.
603 @deftypefn {System Call} int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
604 Reads @var{size} bytes from the file open as @var{fd} into
605 @var{buffer}. Returns the number of bytes actually read (0 at end of
606 file), or -1 if the file could not be read (due to a condition other
607 than end of file). Fd 0 reads from the keyboard using
610 Consider implementing this function in terms of @func{file_read}.
613 @deftypefn {System Call} int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
614 Writes @var{size} bytes from @var{buffer} to the open file @var{fd}.
615 Returns the number of bytes actually written, or -1 if the file could
618 Writing past end-of-file would normally extend the file, but file growth
619 is not implemented by the basic file system. The expected behavior is
620 to write as many bytes as possible up to end-of-file and return the
621 actual number written, or -1 if no bytes could be written at all.
623 Fd 1 writes to the console. Your code to write to the console should
624 write all of @var{buffer} in one call to @func{putbuf}, at least as
625 long as @var{size} is not bigger than a few hundred bytes. Otherwise,
626 lines of text output by different processes may end up interleaved on
627 the console, confusing both human readers and our grading scripts.
629 Consider implementing this function in terms of @func{file_write}.
632 @deftypefn {System Call} void seek (int @var{fd}, unsigned @var{position})
633 Changes the next byte to be read or written in open file @var{fd} to
634 @var{position}, expressed in bytes from the beginning of the file.
635 (Thus, a @var{position} of 0 is the file's start.)
637 A seek past the current end of a file is not an error. A later read
638 obtains 0 bytes, indicating end of file. A later write extends the
639 file, filling any unwritten gap with zeros. (However, in Pintos files
640 have a fixed length until project 4 is complete, so writes past end of
641 file will return an error.) These semantics are implemented in the
642 file system and do not require any special effort in system call
645 Consider implementing this function in terms of @func{file_seek}.
648 @deftypefn {System Call} unsigned tell (int @var{fd})
649 Returns the position of the next byte to be read or written in open
650 file @var{fd}, expressed in bytes from the beginning of the file.
652 Consider implementing this function in terms of @func{file_tell}.
655 @deftypefn {System Call} void close (int @var{fd})
656 Closes file descriptor @var{fd}.
658 Consider implementing this function in terms of @func{file_close}.
661 The file defines other syscalls. Ignore them for now. You will
662 implement some of them in project 3 and the rest in project 4, so be
663 sure to design your system with extensibility in mind.
665 To implement syscalls, you need to provide ways to read and write data
666 in user virtual address space.
667 You need this ability before you can
668 even obtain the system call number, because the system call number is
669 on the user's stack in the user's virtual address space.
670 This can be a bit tricky: what if the user provides an invalid
671 pointer, a pointer into kernel memory, or a block
672 partially in one of those regions? You should handle these cases by
673 terminating the user process. We recommend
674 writing and testing this code before implementing any other system
677 You must synchronize system calls so that
678 any number of user processes can make them at once. In particular, it
679 is not safe to call into the file system code provided in the
680 @file{filesys} directory from multiple threads at once. For now, we
681 recommend adding a single lock that controls access to the file system
682 code. You should acquire this lock before calling any functions in
683 the @file{filesys} directory, and release it afterward. Don't forget
684 that @func{process_execute} also accesses files. @strong{For now, we
685 recommend against modifying code in the @file{filesys} directory.}
687 We have provided you a user-level function for each system call in
688 @file{lib/user/syscall.c}. These provide a way for user processes to
689 invoke each system call from a C program. Each uses a little inline
690 assembly code to invoke the system call and (if appropriate) returns the
691 system call's return value.
693 When you're done with this part, and forevermore, Pintos should be
694 bulletproof. Nothing that a user program can do should ever cause the
695 OS to crash, panic, fail an assertion, or otherwise malfunction. It is
696 important to emphasize this point: our tests will try to break your
697 system calls in many, many ways. You need to think of all the corner
698 cases and handle them. The sole way a user program should be able to
699 cause the OS to halt is by invoking the @code{halt} system call.
701 If a system call is passed an invalid argument, acceptable options
702 include returning an error value (for those calls that return a
703 value), returning an undefined value, or terminating the process.
705 @xref{System Call Details}, for details on how system calls work.
707 @node Denying Writes to Executables
708 @subsection Denying Writes to Executables
710 Add code to deny writes to files in use as executables. Many OSes do
711 this because of the unpredictable results if a process tried to run code
712 that was in the midst of being changed on disk. This is especially
713 important once virtual memory is implemented in project 3, but it can't
716 You can use @func{file_deny_write} to prevent writes to an open file.
717 Calling @func{file_allow_write} on the file will re-enable them (unless
718 the file is denied writes by another opener). Closing a file will also
725 @item How much code will I need to write?
727 Here's a summary of our reference solution, produced by the
728 @command{diffstat} program. The final row gives total lines inserted
729 and deleted; a changed line counts as both an insertion and a deletion.
732 threads/thread.c | 13
733 threads/thread.h | 26 +
734 userprog/exception.c | 8
735 userprog/process.c | 247 ++++++++++++++--
736 userprog/syscall.c | 468 ++++++++++++++++++++++++++++++-
737 userprog/syscall.h | 1
738 6 files changed, 725 insertions(+), 38 deletions(-)
741 @item The kernel always panics when I run @code{pintos -p @var{file} -- -q}.
743 Did you format the disk (with @samp{pintos -f})?
745 Is your file name too long? The file system limits file names to 14
746 characters. A command like @samp{pintos -p ../../examples/echo -- -q}
747 will exceed the limit. Use @samp{pintos -p ../../examples/echo -a echo
748 -- -q} to put the file under the name @file{echo} instead.
750 Is the file system full?
752 Does the file system already contain 16 files? The base Pintos file
753 system has a 16-file limit.
755 The file system may be so fragmented that there's not enough contiguous
758 @item When I run @code{pintos -p ../file --}, @file{file} isn't copied.
760 Files are written under the name you refer to them, by default, so in
761 this case the file copied in would be named @file{../file}. You
762 probably want to run @code{pintos -p ../file -a file --} instead.
764 @item All my user programs die with page faults.
766 This will happen if you haven't implemented argument passing
767 (or haven't done so correctly). The basic C library for user programs tries
768 to read @var{argc} and @var{argv} off the stack. If the stack
769 isn't properly set up, this causes a page fault.
771 @item All my user programs die with @code{system call!}
773 You'll have to implement system calls before you see anything else.
774 Every reasonable program tries to make at least one system call
775 (@func{exit}) and most programs make more than that. Notably,
776 @func{printf} invokes the @code{write} system call. The default system
777 call handler just prints @samp{system call!} and terminates the program.
778 Until then, you can use @func{hex_dump} to convince yourself that
779 argument passing is implemented correctly (@pxref{Program Startup Details}).
781 @item How can I can disassemble user programs?
783 The @command{objdump} (80@var{x}86) or @command{i386-elf-objdump}
784 (SPARC) utility can disassemble entire user
785 programs or object files. Invoke it as @code{objdump -d
786 @var{file}}. You can use @code{gdb}'s
787 @command{disassemble} command to disassemble individual functions
790 @item Why do many C include files not work in Pintos programs?
792 The C library we provide is very limited. It does not include many of
793 the features that are expected of a real operating system's C library.
794 The C library must be built specifically for the operating system (and
795 architecture), since it must make system calls for I/O and memory
796 allocation. (Not all functions do, of course, but usually the library
797 is compiled as a unit.)
799 @item Can I use lib@var{foo} in my Pintos programs?
801 The chances are good that lib@var{foo} uses parts of the C library
802 that Pintos doesn't implement. It will probably take at least some
803 porting effort to make it work under Pintos. Notably, the Pintos
804 user program C library does not have a @func{malloc} implementation.
806 @item How do I compile new user programs?
808 Modify @file{src/examples/Makefile}, then run @command{make}.
810 @item Can I run user programs under a debugger?
812 Yes, with some limitations. @xref{Debugging User Programs}.
814 @item What's the difference between @code{tid_t} and @code{pid_t}?
816 A @code{tid_t} identifies a kernel thread, which may have a user
817 process running in it (if created with @func{process_execute}) or not
818 (if created with @func{thread_create}). It is a data type used only
821 A @code{pid_t} identifies a user process. It is used by user
822 processes and the kernel in the @code{exec} and @code{wait} system
825 You can choose whatever suitable types you like for @code{tid_t} and
826 @code{pid_t}. By default, they're both @code{int}. You can make them
827 a one-to-one mapping, so that the same values in both identify the
828 same process, or you can use a more complex mapping. It's up to you.
830 @item Keyboard input doesn't work with @command{pintos} option @option{-v}.
832 Serial input isn't implemented. Don't use @option{-v} if you
833 want to use the shell or otherwise need keyboard input.
837 * Argument Passing FAQ::
841 @node Argument Passing FAQ
842 @subsection Argument Passing FAQ
845 @item Isn't the top of stack off the top of user virtual memory?
847 The top of stack is at @code{PHYS_BASE}, typically @t{0xc0000000}, which
848 is also where kernel virtual memory starts.
849 But when the processor pushes data on the stack, it decrements the stack
850 pointer first. Thus, the first (4-byte) value pushed on the stack
851 will be at address @t{0xbffffffc}.
853 @item Is @code{PHYS_BASE} fixed?
855 No. You should be able to support @code{PHYS_BASE} values that are
856 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xf0000000},
857 simply via recompilation.
860 @node System Calls FAQ
861 @subsection System Calls FAQ
864 @item Can I just cast a @code{struct file *} to get a file descriptor?
865 @itemx Can I just cast a @code{struct thread *} to a @code{pid_t}?
867 You will have to make these design decisions yourself.
868 Most operating systems do distinguish between file
869 descriptors (or pids) and the addresses of their kernel data
870 structures. You might want to give some thought as to why they do so
871 before committing yourself.
873 @item Can I set a maximum number of open files per process?
875 It is better not to set an arbitrary limit. You may impose a limit of
876 128 open files per process, if necessary.
878 @item What happens when an open file is removed?
879 @anchor{Removing an Open File}
881 You should implement the standard Unix semantics for files. That is, when
882 a file is removed any process which has a file descriptor for that file
883 may continue to use that descriptor. This means that
884 they can read and write from the file. The file will not have a name,
885 and no other processes will be able to open it, but it will continue
886 to exist until all file descriptors referring to the file are closed
887 or the machine shuts down.
889 @item How can I run user programs that need more than 4 kB stack space?
891 You may modify the stack setup code to allocate more than one page of
892 stack space for each process. In the next project, you will implement a
896 @node 80x86 Calling Convention
897 @section 80@var{x}86 Calling Convention
899 This section summarizes important points of the convention used for
900 normal function calls on 32-bit 80@var{x}86 implementations of Unix.
901 Some details are omitted for brevity. If you do want all the details,
902 you can refer to @bibref{SysV-i386}.
904 The basic calling convention works like this:
908 The caller pushes each of the function's arguments on the stack one by
909 one, normally using the @code{PUSH} assembly language instruction.
910 Arguments are pushed in right-to-left order.
913 The caller pushes the address of its next instruction (the @dfn{return
914 address}) on the stack and jumps to the first instruction of the callee.
915 A single 80@var{x}86 instruction, @code{CALL}, does both.
918 The callee executes. When it takes control, the stack pointer points to
919 the return address, the first argument is just above it, the second
920 argument is just above the first argument, and so on.
923 If the callee has a return value, it stores it into register @code{EAX}.
926 The callee returns by popping the return address from the stack and
927 jumping to the location it specifies, using the 80@var{x}86 @code{RET}
931 The caller pops the arguments off the stack.
934 Consider a function @func{f} that takes three @code{int} arguments.
935 This diagram shows a sample stack frame as seen by the callee at the
936 beginning of step 3 above, supposing that @func{f} is invoked as
937 @code{f(1, 2, 3)}. The stack addresses are arbitrary:
950 stack pointer --> 0xbffffe70 | return address |
958 * Program Startup Details::
959 * System Call Details::
962 @node Program Startup Details
963 @subsection Program Startup Details
965 The Pintos C library for user programs designates @func{_start}, in
966 @file{lib/user/entry.c}, as the entry point for user programs. This
967 function is a wrapper around @func{main} that calls @func{exit} if
972 _start (int argc, char *argv[])
974 exit (main (argc, argv));
978 The kernel is responsible for setting up the arguments for the initial
979 function on the stack, in accordance with the calling convention
980 explained in the preceding section, before it allows the user program to
983 Consider the following example command: @samp{/bin/ls -l foo bar}.
984 First, the kernel must break the command into words, as @samp{/bin/ls},
985 @samp{-l}, @samp{foo}, and @samp{bar}, and place them at the top of the
986 stack. Order doesn't matter, because they will be referenced through
989 Then, push the address of each string plus a null pointer sentinel, on
990 the stack, in right-to-left order. These are the elements of
991 @code{argv}. The order ensure that @code{argv[0]} is at the lowest
992 virtual address. Word-aligned accesses are faster than unaligned
993 accesses, so for best performance round the stack pointer down to a
994 multiple of 4 before the first push.
996 Then, push @code{argv} (the address of @code{argv[0]}) and @code{argc},
997 in that order. Finally, push a fake ``return address'': although the
998 entry function will never return, its stack frame must have the same
999 structure as any other.
1001 The table below show the state of the stack and the relevant registers
1002 right before the beginning of the user program, assuming
1003 @code{PHYS_BASE} is @t{0xc0000000}:
1008 @multitable {@t{0xbfffffff}} {return address} {@t{/bin/ls\0}} {@code{void (*) ()}}
1009 @item Address @tab Name @tab Data @tab Type
1010 @item @t{0xbffffffc} @tab @code{argv[3][@dots{}]} @tab @samp{bar\0} @tab @code{char[4]}
1011 @item @t{0xbffffff8} @tab @code{argv[2][@dots{}]} @tab @samp{foo\0} @tab @code{char[4]}
1012 @item @t{0xbffffff5} @tab @code{argv[1][@dots{}]} @tab @samp{-l\0} @tab @code{char[3]}
1013 @item @t{0xbfffffed} @tab @code{argv[0][@dots{}]} @tab @samp{/bin/ls\0} @tab @code{char[8]}
1014 @item @t{0xbfffffec} @tab word-align @tab 0 @tab @code{uint8_t}
1015 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0} @tab @code{char *}
1016 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc} @tab @code{char *}
1017 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8} @tab @code{char *}
1018 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5} @tab @code{char *}
1019 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed} @tab @code{char *}
1020 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8} @tab @code{char **}
1021 @item @t{0xbfffffd0} @tab @code{argc} @tab 4 @tab @code{int}
1022 @item @t{0xbfffffcc} @tab return address @tab 0 @tab @code{void (*) ()}
1028 In this example, the stack pointer would be initialized to
1031 As shown above, your code should start the stack at the very top of
1032 the user virtual address space, in the page just below virtual address
1033 @code{PHYS_BASE} (defined in @file{threads/mmu.h}).
1035 You may find the non-standard @func{hex_dump} function, declared in
1036 @file{<stdio.h>}, useful for debugging your argument passing code.
1037 Here's what it would show in the above example:
1040 bfffffc0 00 00 00 00 | ....|
1041 bfffffd0 04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
1042 bfffffe0 f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
1043 bffffff0 6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
1046 @node System Call Details
1047 @subsection System Call Details
1049 The first project already dealt with one way that the operating system
1050 can regain control from a user program: interrupts from timers and I/O
1051 devices. These are ``external'' interrupts, because they are caused
1052 by entities outside the CPU (@pxref{External Interrupt Handling}).
1054 The operating system also deals with software exceptions, which are
1055 events that occur in program code (@pxref{Internal Interrupt
1056 Handling}). These can be errors such as a page fault or division by
1057 zero. Exceptions are also the means by which a user program
1058 can request services (``system calls'') from the operating system.
1060 In the 80@var{x}86 architecture, the @samp{int} instruction is the
1061 most commonly used means for invoking system calls. This instruction
1062 is handled in the same way as other software exceptions. In Pintos,
1063 user programs invoke @samp{int $0x30} to make a system call. The
1064 system call number and any additional arguments are expected to be
1065 pushed on the stack in the normal fashion before invoking the
1068 Thus, when the system call handler @func{syscall_handler} gets control,
1069 the system call number is in the 32-bit word at the caller's stack
1070 pointer, the first argument is in the 32-bit word at the next higher
1071 address, and so on. The caller's stack pointer is accessible to
1072 @func{syscall_handler} as the @samp{esp} member of the
1073 @struct{intr_frame} passed to it. (@struct{intr_frame} is on the kernel
1076 The 80@var{x}86 convention for function return values is to place them
1077 in the @code{EAX} register. System calls that return a value can do
1078 so by modifying the @samp{eax} member of @struct{intr_frame}.
1080 You should try to avoid writing large amounts of repetitive code for
1081 implementing system calls. Each system call argument, whether an
1082 integer or a pointer, takes up 4 bytes on the stack. You should be able
1083 to take advantage of this to avoid writing much near-identical code for
1084 retrieving each system call's arguments from the stack.