1 @node Project 2--User Programs
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, but you will also be interacting with almost every
14 other part of Pintos. We will describe the
17 You can build project 2 on top of your project 1 submission or you can
18 start fresh. 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.
22 You might find it useful to go back and reread how to run the tests
23 (@pxref{Testing}). In particular, the tests for project 2 and later
24 projects will probably run faster if you use the qemu emulator, e.g.@:
25 via @code{make check PINTOSOPTS='--qemu'}. The qemu emulator is
26 available only on the Linux machines.
29 * Project 2 Background::
30 * Project 2 Suggested Order of Implementation::
31 * Project 2 Requirements::
33 * 80x86 Calling Convention::
36 @node Project 2 Background
39 Up to now, all of the code you have run under Pintos has been part
40 of the operating system kernel. This means, for example, that all the
41 test code from the last assignment ran as part of the kernel, with
42 full access to privileged parts of the system. Once we start running
43 user programs on top of the operating system, this is no longer true.
44 This project deals with the consequences.
46 We allow more than one process to run at a time. Each process has one
47 thread (multithreaded processes are not supported). User programs are
48 written under the illusion that they have the entire machine. This
49 means that when you load and run multiple processes at a time, you must
50 manage memory, scheduling, and other state correctly to maintain this
53 In the previous project, we compiled our test code directly into your
54 kernel, so we had to require certain specific function interfaces within
55 the kernel. From now on, we will test your operating system by running
56 user programs. This gives you much greater freedom. You must make sure
57 that the user program interface meets the specifications described here,
58 but given that constraint you are free to restructure or rewrite kernel
59 code however you wish.
62 * Project 2 Source Files::
63 * Using the File System::
64 * How User Programs Work::
65 * Virtual Memory Layout::
66 * Accessing User Memory::
69 @node Project 2 Source Files
70 @subsection Source Files
72 The easiest way to get an overview of the programming you will be
73 doing is to simply go over each part you'll be working with. In
74 @file{userprog}, you'll find a small number of files, but here is
75 where the bulk of your work will be:
80 Loads ELF binaries and starts processes.
84 A simple manager for 80@var{x}86 hardware page tables.
85 Although you probably won't want to modify this code for this project,
86 you may want to call some of its functions.
87 @xref{Page Tables}, for more information.
91 Whenever a user process wants to access some kernel functionality, it
92 invokes a system call. This is a skeleton system call
93 handler. Currently, it just prints a message and terminates the user
94 process. In part 2 of this project you will add code to do everything
95 else needed by system calls.
99 When a user process performs a privileged or prohibited operation, it
100 traps into the kernel as an ``exception'' or ``fault.''@footnote{We
101 will treat these terms as synonyms. There is no standard
102 distinction between them, although Intel processor manuals make
103 a minor distinction between them on 80@var{x}86.} These files handle
104 exceptions. Currently all exceptions simply print a message and
105 terminate the process. Some, but not all, solutions to project 2
106 require modifying @func{page_fault} in this file.
110 The 80@var{x}86 is a segmented architecture. The Global Descriptor
111 Table (GDT) is a table that describes the segments in use. These
112 files set up the GDT. You should not need to modify these
113 files for any of the projects. You can read the code if
114 you're interested in how the GDT works.
118 The Task-State Segment (TSS) is used for 80@var{x}86 architectural
119 task switching. Pintos uses the TSS only for switching stacks when a
120 user process enters an interrupt handler, as does Linux. You
121 should not need to modify these files for any of the projects.
122 You can read the code if you're interested in how the TSS
126 @node Using the File System
127 @subsection Using the File System
129 You will need to interface to the file system code for this project,
131 user programs are loaded from the file system and many of the
132 system calls you must implement deal with the file system. However,
133 the focus of this project is not the file system, so we have
134 provided a simple but complete file system in the @file{filesys}
136 will want to look over the @file{filesys.h} and @file{file.h}
137 interfaces to understand how to use the file system, and especially
138 its many limitations.
140 There is no need to modify the file system code for this project, and so
141 we recommend that you do not. Working on the file system is likely to
142 distract you from this project's focus.
144 Proper use of the file system routines now
145 will make life much easier for project 4, when you improve the file
146 system implementation. Until then, you will have to tolerate the
147 following limitations:
151 No internal synchronization. Concurrent accesses will interfere with one
152 another. You should use synchronization to ensure that only one process at a
153 time is executing file system code.
156 File size is fixed at creation time. The root directory is
157 represented as a file, so the number of files that may be created is also
161 File data is allocated as a single extent, that is, data in a single
162 file must occupy a contiguous range of sectors on disk. External
163 fragmentation can therefore become a serious problem as a file system is
170 File names are limited to 14 characters.
173 A system crash mid-operation may corrupt the disk in a way
174 that cannot be repaired automatically. There is no file system repair
178 One important feature is included:
182 Unix-like semantics for @func{filesys_remove} are implemented.
183 That is, if a file is open when it is removed, its blocks
184 are not deallocated and it may still be accessed by any
185 threads that have it open, until the last one closes it. @xref{Removing
186 an Open File}, for more information.
189 You need to be able to create simulated disks. The
190 @command{pintos-mkdisk} program provides this functionality. From the
191 @file{userprog/build} directory, execute @code{pintos-mkdisk fs.dsk@tie{}2}.
192 This command creates a 2 MB simulated disk named @file{fs.dsk}. Then
193 format the disk by passing @option{-f -q} on the kernel's command
194 line: @code{pintos -f -q}. The @option{-f} option causes the disk to be
195 formatted, and @option{-q} causes Pintos to exit as soon as the format
198 You'll need a way to copy files in and out of the simulated file system.
199 The @code{pintos} @option{-p} (``put'') and @option{-g} (``get'')
200 options do this. To copy @file{@var{file}} into the
201 Pintos file system, use the command @file{pintos -p @var{file} -- -q}.
202 (The @samp{--} is needed because @option{-p} is for the @command{pintos}
203 script, not for the simulated kernel.) To copy it to the Pintos file
204 system under the name @file{@var{newname}}, add @option{-a
205 @var{newname}}: @file{pintos -p @var{file} -a @var{newname} -- -q}. The
206 commands for copying files out of a VM are similar, but substitute
207 @option{-g} for @option{-p}.
209 Incidentally, these commands work by passing special commands
210 @command{put} and @command{get} on the kernel's command line and copying
211 to and from a special simulated ``scratch'' disk. If you're very
212 curious, you can look at the @command{pintos} script as well as
213 @file{filesys/fsutil.c} to learn the implementation details.
215 Here's a summary of how to create and format a disk, copy the
216 @command{echo} program into the new disk, and then run @command{echo},
217 passing argument @code{x}. (Argument passing won't work until
218 you implemented it.) It assumes
219 that you've already built the
220 examples in @file{examples} and that the current directory is
221 @file{userprog/build}:
224 pintos-mkdisk fs.dsk 2
226 pintos -p ../../examples/echo -a echo -- -q
227 pintos -q run 'echo x'
230 The three final steps can actually be combined into a single command:
233 pintos-mkdisk fs.dsk 2
234 pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'
237 If you don't want to keep the file system disk around for later use or
238 inspection, you can even combine all four steps into a single command.
239 The @code{--fs-disk=@var{n}} option creates a temporary disk
240 approximately @var{n} megabytes in size just for the duration of the
241 @command{pintos} run. The Pintos automatic test suite makes extensive
245 pintos --fs-disk=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'
248 You can delete a file from the Pintos file system using the @code{rm
249 @var{file}} kernel action, e.g.@: @code{pintos -q rm @var{file}}. Also,
250 @command{ls} lists the files in the file system and @code{cat
251 @var{file}} prints a file's contents to the display.
253 @node How User Programs Work
254 @subsection How User Programs Work
256 Pintos can run normal C programs, as long as they fit into memory and use
257 only the system calls you implement. Notably, @func{malloc} cannot be
258 implemented because none of the system calls required for this project
259 allow for memory allocation. Pintos also can't run programs that use
260 floating point operations, since the kernel doesn't save and restore the
261 processor's floating-point unit when switching threads.
263 The @file{src/examples} directory contains a few sample user
264 programs. The @file{Makefile} in this directory
265 compiles the provided examples, and you can edit it
266 compile your own programs as well. Some of the example programs will
267 only work once projects 3 or 4 have been implemented.
269 Pintos can load @dfn{ELF} executables with the loader provided for you
270 in @file{userprog/process.c}. ELF is a file format used by Linux,
271 Solaris, and many other operating systems for object files,
272 shared libraries, and executables. You can actually use any compiler
273 and linker that output 80@var{x}86 ELF executables to produce programs
274 for Pintos. (We've provided compilers and linkers that should do just
277 You should realize immediately that, until you copy a
278 test program to the simulated disk, Pintos will be unable to do
279 useful work. You won't be able to do
280 interesting things until you copy a variety of programs to the disk.
281 You might want to create a clean reference disk and copy that
282 over whenever you trash your @file{fs.dsk} beyond a useful state,
283 which may happen occasionally while debugging.
285 @node Virtual Memory Layout
286 @subsection Virtual Memory Layout
288 Virtual memory in Pintos is divided into two regions: user virtual
289 memory and kernel virtual memory. User virtual memory ranges from
290 virtual address 0 up to @code{PHYS_BASE}, which is defined in
291 @file{threads/vaddr.h} and defaults to @t{0xc0000000} (3 GB). Kernel
292 virtual memory occupies the rest of the virtual address space, from
293 @code{PHYS_BASE} up to 4 GB.
295 User virtual memory is per-process.
296 When the kernel switches from one process to another, it
297 also switches user virtual address spaces by changing the processor's
298 page directory base register (see @func{pagedir_activate} in
299 @file{userprog/pagedir.c}). @struct{thread} contains a pointer to a
300 process's page table.
302 Kernel virtual memory is global. It is always mapped the same way,
303 regardless of what user process or kernel thread is running. In
304 Pintos, kernel virtual memory is mapped one-to-one to physical
305 memory, starting at @code{PHYS_BASE}. That is, virtual address
306 @code{PHYS_BASE} accesses physical
307 address 0, virtual address @code{PHYS_BASE} + @t{0x1234} access
308 physical address @t{0x1234}, and so on up to the size of the machine's
311 A user program can only access its own user virtual memory. An attempt to
312 access kernel virtual memory causes a page fault, handled by
313 @func{page_fault} in @file{userprog/exception.c}, and the process
314 will be terminated. Kernel threads can access both kernel virtual
315 memory and, if a user process is running, the user virtual memory of
316 the running process. However, even in the kernel, an attempt to
317 access memory at an unmapped user virtual address
318 will cause a page fault.
320 You must handle memory fragmentation gracefully, that is, a process that
321 needs @var{N} pages of user virtual memory must not require those pages
322 to be contiguous in physical memory (or, equivalently, in kernel virtual
326 * Typical Memory Layout::
329 @node Typical Memory Layout
330 @subsubsection Typical Memory Layout
332 Conceptually, each process is
333 free to lay out its own user virtual memory however it
334 chooses. In practice, user virtual memory is laid out like this:
341 PHYS_BASE +----------------------------------+
355 +----------------------------------+
356 | uninitialized data segment (BSS) |
357 +----------------------------------+
358 | initialized data segment |
359 +----------------------------------+
361 0x08048000 +----------------------------------+
367 0 +----------------------------------+
374 In this project, the user stack is fixed in size, but in project 3 it
375 will be allowed to grow. Traditionally, the size of the uninitialized
376 data segment can be adjusted with a system call, but you will not have
379 The code segment in Pintos starts at user virtual address
380 @t{0x08084000}, approximately 128 MB from the bottom of the address
381 space. This value is specified in @bibref{SysV-i386} and has no deep
384 The linker sets the layout of a user program in memory, as directed by a
385 ``linker script'' that tells it the names and locations of the various
386 program segments. You can learn more about linker scripts by reading
387 the ``Scripts'' chapter in the linker manual, accessible via @samp{info
390 To view the layout of a particular executable, run @command{objdump}
391 (80@var{x}86) or @command{i386-elf-objdump} (SPARC) with the @option{-p}
394 @node Accessing User Memory
395 @subsection Accessing User Memory
398 call, the kernel must often access memory through pointers provided by a user
399 program. The kernel must be very careful about doing so, because
400 the user can pass a null pointer, a pointer to
401 unmapped virtual memory, or a pointer to kernel virtual address space
402 (above @code{PHYS_BASE}). All of these types of invalid pointers must
403 be rejected without harm to the kernel or other running processes, by
404 terminating the offending process and freeing its resources.
406 There are at least two reasonable ways to do this correctly. The
407 first method is to verify
408 the validity of a user-provided pointer, then dereference it. If you
409 choose this route, you'll want to look at the functions in
410 @file{userprog/pagedir.c} and in @file{threads/vaddr.h}. This is the
411 simplest way to handle user memory access.
413 The second method is to check only that a user
414 pointer points below @code{PHYS_BASE}, then dereference it.
415 An invalid user pointer will cause a ``page fault'' that you can
416 handle by modifying the code for @func{page_fault} in
417 @file{userprog/exception.cc}. This technique is normally faster
418 because it takes advantage of the processor's MMU, so it tends to be
419 used in real kernels (including Linux).
421 In either case, you need to make sure not to ``leak'' resources. For
422 example, suppose that your system call has acquired a lock or
423 allocated memory with @func{malloc}. If you encounter an invalid user pointer
424 afterward, you must still be sure to release the lock or free the page
425 of memory. If you choose to verify user pointers before dereferencing
426 them, this should be straightforward. It's more difficult to handle
427 if an invalid pointer causes a page fault,
428 because there's no way to return an error code from a memory access.
429 Therefore, for those who want to try the latter technique, we'll
430 provide a little bit of helpful code:
433 /* Reads a byte at user virtual address UADDR.
434 UADDR must be below PHYS_BASE.
435 Returns the byte value if successful, -1 if a segfault
438 get_user (const uint8_t *uaddr)
441 asm ("movl $1f, %0; movzbl %1, %0; 1:"
442 : "=&a" (result) : "m" (*uaddr));
446 /* Writes BYTE to user address UDST.
447 UDST must be below PHYS_BASE.
448 Returns true if successful, false if a segfault occurred. */
450 put_user (uint8_t *udst, uint8_t byte)
453 asm ("movl $1f, %0; movb %b2, %1; 1:"
454 : "=&a" (error_code), "=m" (*udst) : "r" (byte));
455 return error_code != -1;
459 Each of these functions assumes that the user address has already been
460 verified to be below @code{PHYS_BASE}. They also assume that you've
461 modified @func{page_fault} so that a page fault in the kernel merely
462 sets @code{eax} to @t{0xffffffff} and copies its former value
465 @node Project 2 Suggested Order of Implementation
466 @section Suggested Order of Implementation
468 We suggest first implementing the following, which can happen in
473 Argument passing (@pxref{Argument Passing}). Every user program will
474 page fault immediately until argument passing is implemented.
476 For now, you may simply wish to change
482 *esp = PHYS_BASE - 12;
484 in @func{setup_stack}. That will work for any test program that doesn't
485 examine its arguments, although its name will be printed as
488 Until you implement argument passing, you should only run programs
489 without passing command-line arguments. Attempting to pass arguments to
490 a program will include those arguments in the name of the program, which
494 User memory access (@pxref{Accessing User Memory}). All system calls
495 need to read user memory. Few system calls need to write to user
499 System call infrastructure (@pxref{System Calls}). Implement enough
500 code to read the system call number from the user stack and dispatch to
501 a handler based on it.
504 The @code{exit} system call. Every user program that finishes in the
505 normal way calls @code{exit}. Even a program that returns from
506 @func{main} calls @code{exit} indirectly (see @func{_start} in
507 @file{lib/user/entry.c}).
510 The @code{write} system call for writing to fd 1, the system console.
511 All of our test programs write to the console (the user process version
512 of @func{printf} is implemented this way), so they will all malfunction
513 until @code{write} is available.
516 For now, change @func{process_wait} to an infinite loop (one that waits
517 forever). The provided implementation returns immediately, so Pintos
518 will power off before any processes actually get to run. You will
519 eventually need to provide a correct implementation.
522 After the above are implemented, user processes should work minimally.
523 At the very least, they can write to the console and exit correctly.
524 You can then refine your implementation so that some of the tests start
527 @node Project 2 Requirements
528 @section Requirements
531 * Project 2 Design Document::
532 * Process Termination Messages::
535 * Denying Writes to Executables::
538 @node Project 2 Design Document
539 @subsection Design Document
541 Before you turn in your project, you must copy @uref{userprog.tmpl, ,
542 the project 2 design document template} into your source tree under the
543 name @file{pintos/src/userprog/DESIGNDOC} and fill it in. We recommend
544 that you read the design document template before you start working on
545 the project. @xref{Project Documentation}, for a sample design document
546 that goes along with a fictitious project.
548 @node Process Termination Messages
549 @subsection Process Termination Messages
551 Whenever a user process terminates, because it called @code{exit}
552 or for any other reason, print the process's name
553 and exit code, formatted as if printed by @code{printf ("%s:
554 exit(%d)\n", @dots{});}. The name printed should be the full name
555 passed to @func{process_execute}, omitting command-line arguments.
556 Do not print these messages when a kernel thread that is not a user
557 process terminates, or
558 when the @code{halt} system call is invoked. The message is optional
559 when a process fails to load.
561 Aside from this, don't print any other
562 messages that Pintos as provided doesn't already print. You may find
563 extra messages useful during debugging, but they will confuse the
564 grading scripts and thus lower your score.
566 @node Argument Passing
567 @subsection Argument Passing
569 Currently, @func{process_execute} does not support passing arguments to
570 new processes. Implement this functionality, by extending
571 @func{process_execute} so that instead of simply taking a program file
572 name as its argument, it divides it into words at spaces. The first
573 word is the program name, the second word is the first argument, and so
574 on. That is, @code{process_execute("grep foo bar")} should run
575 @command{grep} passing two arguments @code{foo} and @code{bar}.
577 Within a command line, multiple spaces are equivalent to a single space,
578 so that @code{process_execute("grep foo bar")} is equivalent to our
579 original example. You can impose a reasonable limit on the length of
580 the command line arguments. For example, you could limit the arguments
581 to those that will fit in a single page (4 kB). (There is an unrelated
582 limit of 128 bytes on command-line arguments that the @command{pintos}
583 utility can pass to the kernel.)
585 You can parse argument strings any way you like. If you're lost,
586 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
587 implemented with thorough comments in @file{lib/string.c}. You can
588 find more about it by looking at the man page (run @code{man strtok_r}
591 @xref{Program Startup Details}, for information on exactly how you
592 need to set up the stack.
595 @subsection System Calls
597 Implement the system call handler in @file{userprog/syscall.c}. The
598 skeleton implementation we provide ``handles'' system calls by
599 terminating the process. It will need to retrieve the system call
600 number, then any system call arguments, and carry out appropriate actions.
602 Implement the following system calls. The prototypes listed are those
603 seen by a user program that includes @file{lib/user/syscall.h}. (This
604 header, and all others in @file{lib/user}, are for use by user
605 programs only.) System call numbers for each system call are defined in
606 @file{lib/syscall-nr.h}:
608 @deftypefn {System Call} void halt (void)
609 Terminates Pintos by calling @func{power_off} (declared in
610 @file{threads/init.h}). This should be seldom used, because you lose
611 some information about possible deadlock situations, etc.
614 @deftypefn {System Call} void exit (int @var{status})
615 Terminates the current user program, returning @var{status} to the
616 kernel. If the process's parent @code{wait}s for it (see below), this
618 that will be returned. Conventionally, a @var{status} of 0 indicates
619 success and nonzero values indicate errors.
622 @deftypefn {System Call} pid_t exec (const char *@var{cmd_line})
623 Runs the executable whose name is given in @var{cmd_line}, passing any
624 given arguments, and returns the new process's program id (pid). Must
625 return pid -1, which otherwise should not be a valid pid, if
626 the program cannot load or run for any reason.
629 @deftypefn {System Call} int wait (pid_t @var{pid})
630 Waits for process @var{pid} to die and returns the status it passed to
631 @code{exit}. Returns -1 if @var{pid}
632 was terminated by the kernel (e.g.@: killed due to an exception). If
633 @var{pid} is does not refer to a child of the
634 calling thread, or if @code{wait} has already been successfully
635 called for the given @var{pid}, returns -1 immediately, without
638 You must ensure that Pintos does not terminate until the initial
639 process exits. The supplied Pintos code tries to do this by calling
640 @func{process_wait} (in @file{userprog/process.c}) from @func{main}
641 (in @file{threads/init.c}). We suggest that you implement
642 @func{process_wait} according to the comment at the top of the
643 function and then implement the @code{wait} system call in terms of
646 All of a process's resources, including its @struct{thread}, must be
647 freed whether its parent ever waits for it or not, and regardless of
648 whether the child exits before or after its parent.
650 Children are not inherited: if @var{A} has child @var{B} and
651 @var{B} has child @var{C}, then @code{wait(C)} always returns immediately
652 when called from @var{A}, even if @var{B} is dead.
654 Consider all the ways a wait can occur: nested waits (@var{A} waits
655 for @var{B}, then @var{B} waits for @var{C}), multiple waits (@var{A}
656 waits for @var{B}, then @var{A} waits for @var{C}), and so on.
658 Implementing this system call requires considerably more work than any
662 @deftypefn {System Call} bool create (const char *@var{file}, unsigned @var{initial_size})
663 Creates a new file called @var{file} initially @var{initial_size} bytes
664 in size. Returns true if successful, false otherwise.
667 @deftypefn {System Call} bool remove (const char *@var{file})
668 Deletes the file called @var{file}. Returns true if successful, false
672 @deftypefn {System Call} int open (const char *@var{file})
673 Opens the file called @var{file}. Returns a nonnegative integer handle
674 called a ``file descriptor'' (fd), or -1 if the file could not be
677 File descriptors numbered 0 and 1 are reserved for the console: fd 0
678 (@code{STDIN_FILENO}) is standard input, fd 1 (@code{STDOUT_FILENO}) is
679 standard output. The @code{open} system call will never return either
680 of these file descriptors, which are valid as system call arguments only
681 as explicitly described below.
683 Each process has an independent set of file descriptors. File
684 descriptors are not inherited by child processes.
687 @deftypefn {System Call} int filesize (int @var{fd})
688 Returns the size, in bytes, of the file open as @var{fd}.
691 @deftypefn {System Call} int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
692 Reads @var{size} bytes from the file open as @var{fd} into
693 @var{buffer}. Returns the number of bytes actually read (0 at end of
694 file), or -1 if the file could not be read (due to a condition other
695 than end of file). Fd 0 reads from the keyboard using
696 @func{kbd_getc}. (Keyboard input will not work if you pass the
697 @option{-v} option to @command{pintos}.)
700 @deftypefn {System Call} int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
701 Writes @var{size} bytes from @var{buffer} to the open file @var{fd}.
702 Returns the number of bytes actually written, or -1 if the file could
705 Writing past end-of-file would normally extend the file, but file growth
706 is not implemented by the basic file system. The expected behavior is
707 to write as many bytes as possible up to end-of-file and return the
708 actual number written, or -1 if no bytes could be written at all.
710 Fd 1 writes to the console. Your code to write to the console should
711 write all of @var{buffer} in one call to @func{putbuf}, at least as
712 long as @var{size} is not bigger than a few hundred bytes. (It is
713 reasonable to break up larger buffers.) Otherwise,
714 lines of text output by different processes may end up interleaved on
715 the console, confusing both human readers and our grading scripts.
718 @deftypefn {System Call} void seek (int @var{fd}, unsigned @var{position})
719 Changes the next byte to be read or written in open file @var{fd} to
720 @var{position}, expressed in bytes from the beginning of the file.
721 (Thus, a @var{position} of 0 is the file's start.)
723 A seek past the current end of a file is not an error. A later read
724 obtains 0 bytes, indicating end of file. A later write extends the
725 file, filling any unwritten gap with zeros. (However, in Pintos files
726 have a fixed length until project 4 is complete, so writes past end of
727 file will return an error.) These semantics are implemented in the
728 file system and do not require any special effort in system call
732 @deftypefn {System Call} unsigned tell (int @var{fd})
733 Returns the position of the next byte to be read or written in open
734 file @var{fd}, expressed in bytes from the beginning of the file.
737 @deftypefn {System Call} void close (int @var{fd})
738 Closes file descriptor @var{fd}.
739 Exiting or terminating a process implicitly closes all its open file
740 descriptors, as if by calling this function for each one.
743 The file defines other syscalls. Ignore them for now. You will
744 implement some of them in project 3 and the rest in project 4, so be
745 sure to design your system with extensibility in mind.
747 To implement syscalls, you need to provide ways to read and write data
748 in user virtual address space.
749 You need this ability before you can
750 even obtain the system call number, because the system call number is
751 on the user's stack in the user's virtual address space.
752 This can be a bit tricky: what if the user provides an invalid
753 pointer, a pointer into kernel memory, or a block
754 partially in one of those regions? You should handle these cases by
755 terminating the user process. We recommend
756 writing and testing this code before implementing any other system
757 call functionality. @xref{Accessing User Memory}, for more information.
759 You must synchronize system calls so that
760 any number of user processes can make them at once. In particular, it
761 is not safe to call into the file system code provided in the
762 @file{filesys} directory from multiple threads at once. Your system
763 call implementation must treat the file system code as a critical
764 section. Don't forget
765 that @func{process_execute} also accesses files. For now, we
766 recommend against modifying code in the @file{filesys} directory.
768 We have provided you a user-level function for each system call in
769 @file{lib/user/syscall.c}. These provide a way for user processes to
770 invoke each system call from a C program. Each uses a little inline
771 assembly code to invoke the system call and (if appropriate) returns the
772 system call's return value.
774 When you're done with this part, and forevermore, Pintos should be
775 bulletproof. Nothing that a user program can do should ever cause the
776 OS to crash, panic, fail an assertion, or otherwise malfunction. It is
777 important to emphasize this point: our tests will try to break your
778 system calls in many, many ways. You need to think of all the corner
779 cases and handle them. The sole way a user program should be able to
780 cause the OS to halt is by invoking the @code{halt} system call.
782 If a system call is passed an invalid argument, acceptable options
783 include returning an error value (for those calls that return a
784 value), returning an undefined value, or terminating the process.
786 @xref{System Call Details}, for details on how system calls work.
788 @node Denying Writes to Executables
789 @subsection Denying Writes to Executables
791 Add code to deny writes to files in use as executables. Many OSes do
792 this because of the unpredictable results if a process tried to run code
793 that was in the midst of being changed on disk. This is especially
794 important once virtual memory is implemented in project 3, but it can't
797 You can use @func{file_deny_write} to prevent writes to an open file.
798 Calling @func{file_allow_write} on the file will re-enable them (unless
799 the file is denied writes by another opener). Closing a file will also
800 re-enable writes. Thus, to deny writes to a process's executable, you
801 must keep it open as long as the process is still running.
807 @item How much code will I need to write?
809 Here's a summary of our reference solution, produced by the
810 @command{diffstat} program. The final row gives total lines inserted
811 and deleted; a changed line counts as both an insertion and a deletion.
813 The reference solution represents just one possible solution. Many
814 other solutions are also possible and many of those differ greatly from
815 the reference solution. Some excellent solutions may not modify all the
816 files modified by the reference solution, and some may modify files not
817 modified by the reference solution.
820 threads/thread.c | 13
821 threads/thread.h | 26 +
822 userprog/exception.c | 8
823 userprog/process.c | 247 ++++++++++++++--
824 userprog/syscall.c | 468 ++++++++++++++++++++++++++++++-
825 userprog/syscall.h | 1
826 6 files changed, 725 insertions(+), 38 deletions(-)
829 @item The kernel always panics when I run @code{pintos -p @var{file} -- -q}.
831 Did you format the disk (with @samp{pintos -f})?
833 Is your file name too long? The file system limits file names to 14
834 characters. A command like @samp{pintos -p ../../examples/echo -- -q}
835 will exceed the limit. Use @samp{pintos -p ../../examples/echo -a echo
836 -- -q} to put the file under the name @file{echo} instead.
838 Is the file system full?
840 Does the file system already contain 16 files? The base Pintos file
841 system has a 16-file limit.
843 The file system may be so fragmented that there's not enough contiguous
846 @item When I run @code{pintos -p ../file --}, @file{file} isn't copied.
848 Files are written under the name you refer to them, by default, so in
849 this case the file copied in would be named @file{../file}. You
850 probably want to run @code{pintos -p ../file -a file --} instead.
852 @item All my user programs die with page faults.
854 This will happen if you haven't implemented argument passing
855 (or haven't done so correctly). The basic C library for user programs tries
856 to read @var{argc} and @var{argv} off the stack. If the stack
857 isn't properly set up, this causes a page fault.
859 @item All my user programs die with @code{system call!}
861 You'll have to implement system calls before you see anything else.
862 Every reasonable program tries to make at least one system call
863 (@func{exit}) and most programs make more than that. Notably,
864 @func{printf} invokes the @code{write} system call. The default system
865 call handler just prints @samp{system call!} and terminates the program.
866 Until then, you can use @func{hex_dump} to convince yourself that
867 argument passing is implemented correctly (@pxref{Program Startup Details}).
869 @item How can I can disassemble user programs?
871 The @command{objdump} (80@var{x}86) or @command{i386-elf-objdump}
872 (SPARC) utility can disassemble entire user
873 programs or object files. Invoke it as @code{objdump -d
874 @var{file}}. You can use GDB's
875 @code{disassemble} command to disassemble individual functions
878 @item Why do many C include files not work in Pintos programs?
879 @itemx Can I use lib@var{foo} in my Pintos programs?
881 The C library we provide is very limited. It does not include many of
882 the features that are expected of a real operating system's C library.
883 The C library must be built specifically for the operating system (and
884 architecture), since it must make system calls for I/O and memory
885 allocation. (Not all functions do, of course, but usually the library
886 is compiled as a unit.)
888 The chances are good that the library you want uses parts of the C library
889 that Pintos doesn't implement. It will probably take at least some
890 porting effort to make it work under Pintos. Notably, the Pintos
891 user program C library does not have a @func{malloc} implementation.
893 @item How do I compile new user programs?
895 Modify @file{src/examples/Makefile}, then run @command{make}.
897 @item Can I run user programs under a debugger?
899 Yes, with some limitations. @xref{Debugging User Programs}.
901 @item What's the difference between @code{tid_t} and @code{pid_t}?
903 A @code{tid_t} identifies a kernel thread, which may have a user
904 process running in it (if created with @func{process_execute}) or not
905 (if created with @func{thread_create}). It is a data type used only
908 A @code{pid_t} identifies a user process. It is used by user
909 processes and the kernel in the @code{exec} and @code{wait} system
912 You can choose whatever suitable types you like for @code{tid_t} and
913 @code{pid_t}. By default, they're both @code{int}. You can make them
914 a one-to-one mapping, so that the same values in both identify the
915 same process, or you can use a more complex mapping. It's up to you.
917 @item Keyboard input doesn't work.
919 You are probably passing @option{-v} to @command{pintos}, but
920 serial input isn't implemented. Don't use @option{-v} if you
921 want to use the shell or otherwise need keyboard input.
925 * Argument Passing FAQ::
929 @node Argument Passing FAQ
930 @subsection Argument Passing FAQ
933 @item Isn't the top of stack in kernel virtual memory?
935 The top of stack is at @code{PHYS_BASE}, typically @t{0xc0000000}, which
936 is also where kernel virtual memory starts.
937 But before the processor pushes data on the stack, it decrements the stack
938 pointer. Thus, the first (4-byte) value pushed on the stack
939 will be at address @t{0xbffffffc}.
941 @item Is @code{PHYS_BASE} fixed?
943 No. You should be able to support @code{PHYS_BASE} values that are
944 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xf0000000},
945 simply via recompilation.
948 @node System Calls FAQ
949 @subsection System Calls FAQ
952 @item Can I just cast a @code{struct file *} to get a file descriptor?
953 @itemx Can I just cast a @code{struct thread *} to a @code{pid_t}?
955 You will have to make these design decisions yourself.
956 Most operating systems do distinguish between file
957 descriptors (or pids) and the addresses of their kernel data
958 structures. You might want to give some thought as to why they do so
959 before committing yourself.
961 @item Can I set a maximum number of open files per process?
963 It is better not to set an arbitrary limit. You may impose a limit of
964 128 open files per process, if necessary.
966 @item What happens when an open file is removed?
967 @anchor{Removing an Open File}
969 You should implement the standard Unix semantics for files. That is, when
970 a file is removed any process which has a file descriptor for that file
971 may continue to use that descriptor. This means that
972 they can read and write from the file. The file will not have a name,
973 and no other processes will be able to open it, but it will continue
974 to exist until all file descriptors referring to the file are closed
975 or the machine shuts down.
977 @item How can I run user programs that need more than 4 kB stack space?
979 You may modify the stack setup code to allocate more than one page of
980 stack space for each process. In the next project, you will implement a
984 @node 80x86 Calling Convention
985 @section 80@var{x}86 Calling Convention
987 This section summarizes important points of the convention used for
988 normal function calls on 32-bit 80@var{x}86 implementations of Unix.
989 Some details are omitted for brevity. If you do want all the details,
990 refer to @bibref{SysV-i386}.
992 The calling convention works like this:
996 The caller pushes each of the function's arguments on the stack one by
997 one, normally using the @code{PUSH} assembly language instruction.
998 Arguments are pushed in right-to-left order.
1000 The stack grows downward: each push decrements the stack pointer, then
1001 stores into the location it now points to, like the C expression
1002 @samp{*--sp = @var{value}}.
1005 The caller pushes the address of its next instruction (the @dfn{return
1006 address}) on the stack and jumps to the first instruction of the callee.
1007 A single 80@var{x}86 instruction, @code{CALL}, does both.
1010 The callee executes. When it takes control, the stack pointer points to
1011 the return address, the first argument is just above it, the second
1012 argument is just above the first argument, and so on.
1015 If the callee has a return value, it stores it into register @code{EAX}.
1018 The callee returns by popping the return address from the stack and
1019 jumping to the location it specifies, using the 80@var{x}86 @code{RET}
1023 The caller pops the arguments off the stack.
1026 Consider a function @func{f} that takes three @code{int} arguments.
1027 This diagram shows a sample stack frame as seen by the callee at the
1028 beginning of step 3 above, supposing that @func{f} is invoked as
1029 @code{f(1, 2, 3)}. The initial stack address is arbitrary:
1039 stack pointer --> 0xbffffe70 | return address |
1047 * Program Startup Details::
1048 * System Call Details::
1051 @node Program Startup Details
1052 @subsection Program Startup Details
1054 The Pintos C library for user programs designates @func{_start}, in
1055 @file{lib/user/entry.c}, as the entry point for user programs. This
1056 function is a wrapper around @func{main} that calls @func{exit} if
1057 @func{main} returns:
1061 _start (int argc, char *argv[])
1063 exit (main (argc, argv));
1067 The kernel must put the arguments for the initial function on the stack
1068 before it allows the user program to begin executing. The arguments are
1069 passed in the same way as the normal calling convention (@pxref{80x86
1070 Calling Convention}).
1072 Consider how to handle arguments for the following example command:
1073 @samp{/bin/ls -l foo bar}.
1074 First, break the command into words: @samp{/bin/ls},
1075 @samp{-l}, @samp{foo}, @samp{bar}. Place the words at the top of the
1076 stack. Order doesn't matter, because they will be referenced through
1079 Then, push the address of each string plus a null pointer sentinel, on
1080 the stack, in right-to-left order. These are the elements of
1081 @code{argv}. The order ensure that @code{argv[0]} is at the lowest
1082 virtual address. Word-aligned accesses are faster than unaligned
1083 accesses, so for best performance round the stack pointer down to a
1084 multiple of 4 before the first push.
1086 Then, push @code{argv} (the address of @code{argv[0]}) and @code{argc},
1087 in that order. Finally, push a fake ``return address'': although the
1088 entry function will never return, its stack frame must have the same
1089 structure as any other.
1091 The table below show the state of the stack and the relevant registers
1092 right before the beginning of the user program, assuming
1093 @code{PHYS_BASE} is @t{0xc0000000}:
1098 @multitable {@t{0xbfffffff}} {return address} {@t{/bin/ls\0}} {@code{void (*) ()}}
1099 @item Address @tab Name @tab Data @tab Type
1100 @item @t{0xbffffffc} @tab @code{argv[3][@dots{}]} @tab @samp{bar\0} @tab @code{char[4]}
1101 @item @t{0xbffffff8} @tab @code{argv[2][@dots{}]} @tab @samp{foo\0} @tab @code{char[4]}
1102 @item @t{0xbffffff5} @tab @code{argv[1][@dots{}]} @tab @samp{-l\0} @tab @code{char[3]}
1103 @item @t{0xbfffffed} @tab @code{argv[0][@dots{}]} @tab @samp{/bin/ls\0} @tab @code{char[8]}
1104 @item @t{0xbfffffec} @tab word-align @tab 0 @tab @code{uint8_t}
1105 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0} @tab @code{char *}
1106 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc} @tab @code{char *}
1107 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8} @tab @code{char *}
1108 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5} @tab @code{char *}
1109 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed} @tab @code{char *}
1110 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8} @tab @code{char **}
1111 @item @t{0xbfffffd0} @tab @code{argc} @tab 4 @tab @code{int}
1112 @item @t{0xbfffffcc} @tab return address @tab 0 @tab @code{void (*) ()}
1118 In this example, the stack pointer would be initialized to
1121 As shown above, your code should start the stack at the very top of
1122 the user virtual address space, in the page just below virtual address
1123 @code{PHYS_BASE} (defined in @file{threads/vaddr.h}).
1125 You may find the non-standard @func{hex_dump} function, declared in
1126 @file{<stdio.h>}, useful for debugging your argument passing code.
1127 Here's what it would show in the above example:
1130 bfffffc0 00 00 00 00 | ....|
1131 bfffffd0 04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
1132 bfffffe0 f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
1133 bffffff0 6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
1136 @node System Call Details
1137 @subsection System Call Details
1139 The first project already dealt with one way that the operating system
1140 can regain control from a user program: interrupts from timers and I/O
1141 devices. These are ``external'' interrupts, because they are caused
1142 by entities outside the CPU (@pxref{External Interrupt Handling}).
1144 The operating system also deals with software exceptions, which are
1145 events that occur in program code (@pxref{Internal Interrupt
1146 Handling}). These can be errors such as a page fault or division by
1147 zero. Exceptions are also the means by which a user program
1148 can request services (``system calls'') from the operating system.
1150 In the 80@var{x}86 architecture, the @samp{int} instruction is the
1151 most commonly used means for invoking system calls. This instruction
1152 is handled in the same way as other software exceptions. In Pintos,
1153 user programs invoke @samp{int $0x30} to make a system call. The
1154 system call number and any additional arguments are expected to be
1155 pushed on the stack in the normal fashion before invoking the
1156 interrupt (@pxref{80x86 Calling Convention}).
1158 Thus, when the system call handler @func{syscall_handler} gets control,
1159 the system call number is in the 32-bit word at the caller's stack
1160 pointer, the first argument is in the 32-bit word at the next higher
1161 address, and so on. The caller's stack pointer is accessible to
1162 @func{syscall_handler} as the @samp{esp} member of the
1163 @struct{intr_frame} passed to it. (@struct{intr_frame} is on the kernel
1166 The 80@var{x}86 convention for function return values is to place them
1167 in the @code{EAX} register. System calls that return a value can do
1168 so by modifying the @samp{eax} member of @struct{intr_frame}.
1170 You should try to avoid writing large amounts of repetitive code for
1171 implementing system calls. Each system call argument, whether an
1172 integer or a pointer, takes up 4 bytes on the stack. You should be able
1173 to take advantage of this to avoid writing much near-identical code for
1174 retrieving each system call's arguments from the stack.