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 familiar with its
5 infrastructure and thread package, it's time to start working on the
6 parts of the system that will allow users to run programs on top of
7 your operating system. The base code already supports loading and
8 running a single user program at a time with little interactivity
9 possible. You will allow multiple programs to be loaded in at once,
10 and to interact with 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
15 relevant parts below. If you are confident in your HW1 code, you can
16 build on top of it. However, if you wish you can start with a fresh
17 copy of the code and re-implement @func{thread_join}, which is the
18 only part of project #1 required for this assignment.
20 Up to now, all of the code you have written for Pintos has been part
21 of the operating system kernel. This means, for example, that all the
22 test code from the last assignment ran as part of the kernel, with
23 full access to privileged parts of the system. Once we start running
24 user programs on top of the operating system, this is no longer true.
25 This project deals with consequences of the change.
27 We allow more than one user program to run at a time. Because user
28 programs are written and compiled to work under the illusion that they
29 have the entire machine, when you load into memory and run more than
30 one process at a time, you must manage things correctly to maintain
33 Before we delve into the details of the new code that you'll be
34 working with, you should probably undo the test cases from project 1.
38 * Using the File System::
39 * How User Programs Work::
40 * Virtual Memory Layout::
41 * Grading Requirements::
42 * Problem 2-1 Argument Passing::
43 * Problem 2-2 System Calls::
45 * 80x86 Calling Convention::
52 The easiest way to get an overview of the programming you will be
53 doing is to simply go over each part you'll be working with. In
54 @file{userprog}, you'll find a small number of files, but here is
55 where the bulk of your work will be:
60 Loads ELF binaries and starts processes.
64 A simple manager for 80@var{x} page directories and page tables.
65 Although you probably won't want to modify this code for this project,
66 you may want to call some of its functions. In particular,
67 @func{pagedir_get_page} may be helpful for accessing user memory.
71 Whenever a user process wants to access some kernel functionality, it
72 needs to do so via a system call. This is a skeleton system call
73 handler. Currently, it just prints a message and terminates the user
74 process. In part 2 of this project you will add code to do everything
75 else needed by system calls.
79 When a user process performs a privileged or prohibited operation, it
80 traps into the kernel as an ``exception'' or ``fault.''@footnote{We
81 will treat these terms as synonymous. There is no standard
82 distinction between them, although the Intel processor manuals define
83 them slightly differently on 80@var{x}86.} These files handle
84 exceptions. Currently all exceptions simply print a message and
85 terminate the process. Some, but not all, solutions to project 2
86 require modifying @func{page_fault} in this file.
90 The 80@var{x}86 is a segmented architecture. The Global Descriptor
91 Table (GDT) is a table that describes the segments in use. These
92 files set up the GDT. @strong{You should not need to modify these
93 files for any of the projects.} However, you can read the code if
94 you're interested in how the GDT works.
98 The Task-State Segment (TSS) is used for 80@var{x}86 architectural
99 task switching. Pintos uses the TSS only for switching stacks when a
100 user process enters an interrupt handler, as does Linux. @strong{You
101 should not need to modify these files for any of the projects.}
102 However, you can read the code if you're interested in how the TSS
106 Finally, in @file{lib/kernel}, you might want to use
107 @file{bitmap.[ch]}. A bitmap is basically an array of bits, each of
108 which can be true or false. Bitmaps are typically used to keep track
109 of the usage of a large array of (identical) resources: if resource
110 @var{n} is in use, then bit @var{n} of the bitmap is true. You might
111 find it useful for tracking memory pages, for example.
113 @node Using the File System
114 @section Using the File System
116 You will need to use some file system code for this project. First,
117 user programs are loaded from the file system. Second, many of the
118 system calls you must implement deal with the file system. However,
119 the focus of this project is not on the file system code, so we have
120 provided a simple file system in the @file{filesys} directory. You
121 will want to look over the @file{filesys.h} and @file{file.h}
122 interfaces to understand how to use the file system, and especially
123 its many limitations. @strong{You should not modify the file system
124 code for this project}. Proper use of the file system routines now
125 will make life much easier for project 4, when you improve the file
126 system implementation. Until then, you will have to put up with the
127 following limitations:
131 No synchronization. Concurrent accesses will interfere with one
132 another, so external synchronization is needed. @xref{Synchronizing
133 File Access}, for more details.
136 File size is fixed at creation time. Because the root directory is
137 represented as a file, the number of files that may be created is also
141 File data is allocated as a single extent, that is, data in a single
142 file must occupy a contiguous range of sectors on disk. External
143 fragmentation can therefore become a serious problem as a file system is
150 File names are limited to 14 characters.
153 A system crash mid-operation may corrupt the disk in a way
154 that cannot be repaired automatically. No `fsck' tool is
155 provided in any case.
158 However one important feature is included:
162 Unix-like semantics for filesys_remove() are implemented.
163 That is, if a file is open when it is removed, its blocks
164 are not deallocated and it may still be accessed by the
165 threads that have it open until the last one closes it. @xref{Removing
166 an Open File}, for more information.
169 You need to be able to create and format simulated disks. The
170 @command{pintos} program provides this functionality with its
171 @option{make-disk} command. From the @file{userprog/build} directory,
172 execute @code{pintos make-disk fs.dsk 2}. This command creates a 2 MB
173 simulated disk named @file{fs.dsk}. (It does not actually start
174 Pintos.) Then format the disk by passing the @option{-f} option to
175 Pintos on the kernel's command line: @code{pintos run -f}.
177 You'll need a way to get files in and out of the simulated file
178 system. The @code{pintos} @option{put} and @option{get} commands are
179 designed for this. To copy @file{@var{file}} into the Pintos file
180 system, use the command @file{pintos put @var{file}}. To copy it to
181 the Pintos file system under the name @file{@var{newname}}, add the
182 new name to the end of the command: @file{pintos put @var{file}
183 @var{newname}}. The commands for copying files out of a VM are
184 similar, but substitute @option{get} for @option{get}.
186 Incidentally, these commands work by passing special options
187 @option{-ci} and @option{-co} on the kernel's command line and copying
188 to and from a special simulated disk named @file{scratch.dsk}. If
189 you're very curious, you can look at the @command{pintos} program as
190 well as @file{filesys/fsutil.c} to learn the implementation details,
191 but it's really not relevant for this project.
193 Here's a summary of how you would create and format a disk, copy the
194 @command{echo} program into the new disk, and then run @command{echo}.
195 It assumes that you've already built the tests in
196 @file{tests/userprog} and that the current directory is
197 @file{userprog/build}:
200 pintos make-disk fs.dsk 2
202 pintos put ../../tests/userprog/echo echo
206 You can delete a file from the Pintos file system using the @option{-r
207 @var{file}} kernel option, e.g.@: @code{pintos run -r @var{file}}.
208 Also, @option{-ls} lists the files in the file system and @option{-p
209 @var{file}} prints a file's contents to the display.
211 @node How User Programs Work
212 @section How User Programs Work
214 Pintos can run normal C programs. In fact, it can run any program you
215 want, provided it's compiled into the proper file format, and uses
216 only the system calls you implement. (For example, @func{malloc}
217 makes use of functionality that isn't provided by any of the syscalls
218 we require you to support.) The only other limitation is that Pintos
219 can't run programs using floating point operations, since it doesn't
220 include the necessary kernel functionality to save and restore the
221 processor's floating-point unit when switching threads. You can look
222 in @file{tests/userprog} directory for some examples.
224 Pintos loads ELF executables, where ELF is an executable format used
225 by Linux, Solaris, and many other Unix and Unix-like systems.
226 Therefore, you can use any compiler and linker that produce
227 80@var{x}86 ELF executables to produce programs for Pintos. We
228 recommend using the tools we provide in the @file{tests/userprog}
229 directory. By default, the @file{Makefile} in this directory will
230 compile the test programs we provide. You can edit the
231 @file{Makefile} to compile your own test programs as well.
233 One thing you should realize immediately is that, until you copy a
234 test program to the emulated disk, Pintos will be unable to do very
235 much useful work. You will also find that you won't be able to do
236 interesting things until you copy a variety of programs to the disk.
237 A useful technique is to create a clean reference disk and copy that
238 over whenever you trash your @file{fs.dsk} beyond a useful state,
239 which may happen occasionally while debugging.
241 @node Virtual Memory Layout
242 @section Virtual Memory Layout
244 Virtual memory in Pintos is divided into two regions: user virtual
245 memory and kernel virtual memory. User virtual memory ranges from
246 virtual address 0 up to @code{PHYS_BASE}, which is defined in
247 @file{threads/mmu.h} and defaults to @t{0xc0000000} (3 GB). Kernel
248 virtual memory occupies the rest of the virtual address space, from
249 @code{PHYS_BASE} up to 4 GB.
251 User virtual memory is per-process. Conceptually, each process is
252 free to use the entire space of user virtual memory however it
253 chooses. When the kernel switches from one process to another, it
254 also switches user virtual address spaces by switching the processor's
255 page directory base register (see @func{pagedir_activate in
256 @file{userprog/pagedir.c}}. @struct{thread} contains a pointer to a
257 process's page directory.
259 Kernel virtual memory is global. It is always mapped the same way,
260 regardless of what user process or kernel thread is running. In
261 Pintos, kernel virtual memory is mapped one-to-one to physical
262 memory. That is, virtual address @code{PHYS_ADDR} accesses physical
263 address 0, virtual address @code{PHYS_ADDR} + @t{0x1234} access
264 physical address @t{0x1234}, and so on up to the size of the machine's
267 User programs can only access user virtual memory. An attempt to
268 access kernel virtual memory will cause a page fault, handled by
269 @func{page_fault} in @file{userprog/exception.c}, and the process
270 will be terminated. Kernel threads can access both kernel virtual
271 memory and, if a user process is running, the user virtual memory of
272 the running process. However, even in the kernel, an attempt to
273 access memory at a user virtual address that doesn't have a page
274 mapped into it will cause a page fault.
276 You must handle memory fragmentation gracefully, that is, a process
277 that needs @var{N} pages of memory must not require that all @var{N}
278 be contiguous. In fact, it must not require that any of the pages be
281 @node Grading Requirements
282 @section Grading Requirements
284 For testing and grading purposes, we have some simple overall
289 The kernel should print out the program's name and exit status whenever
290 a process terminates, whether termination is caused by the @code{exit}
291 system call or for another reason.
295 The message must be formatted exactly as if it was printed with
296 @code{printf ("%s: exit(%d)\n", @dots{});} given appropriate arguments.
299 The name printed should be the full name passed to
300 @func{process_execute}, except that it is acceptable to truncate it to
301 15 characters to allow for the limited space in @struct{thread}. The
302 name printed need not include arguments.
305 Do not print a message when a kernel thread that is not a process
309 Do not print messages about process termination for the @code{halt}
313 No message need be printed when a process fails to load.
317 Aside from this, the kernel should print out no other messages that
318 Pintos as provided doesn't already print. You
319 may understand all those debug messages, but we won't, and it just
320 clutters our ability to see the stuff we care about.
323 Additionally, while it may be useful to hard-code which process will
324 run at startup while debugging, before you submit your code you must
325 make sure that it takes the start-up process name and arguments from
326 the @samp{-ex} argument. For example, running @code{pintos run -ex
327 "testprogram 1 2 3 4"} will spawn @samp{testprogram 1 2 3 4} as the
331 In the previous project, we required that you provided some specific
332 function interfaces, because we tested your project by compiling our
333 test code into it. For this project and all later projects, this is
334 no longer necessary, because we will do all of our testing with user
335 programs. You must make sure that the user program interface meets
336 the specifications described in the assignments, but given that
337 constraint you are free to restructure or rewrite kernel code however
341 @node Problem 2-1 Argument Passing
342 @section Problem 2-1: Argument Passing
344 Currently, @func{process_execute} does not support passing arguments
345 to new processes. UNIX and other operating systems do allow passing
346 command line arguments to a program, which accesses them via the argc,
347 argv arguments to main. You must implement this functionality by
348 extending @func{process_execute} so that instead of simply taking a
349 program file name as its argument, it divides it into words at spaces.
350 The first word is the program name, the second word is the first
351 argument, and so on. That is, @code{process_execute("grep foo bar")}
352 should run @command{grep} passing two arguments @code{foo} and
353 @file{bar}. A few details:
357 Multiple spaces are considered the same as a single space, so that
358 @code{process_execute("grep foo bar")} would be equivalent to our
362 You can impose a reasonable limit on the length of the command line
363 arguments. For example, you could limit the arguments to those that
364 will fit in a single page (4 kB).
367 You can parse the argument strings any way you like. If you're lost,
368 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
369 implemented with thorough comments in @file{lib/string.c}. You can
370 find more about it by looking at the man page (run @code{man strtok_r}
374 @xref{80x86 Calling Convention}, for information on exactly how you
375 need to set up the stack.
378 @strong{This functionality is extremely important.} Almost all our
379 test cases rely on being able to pass arguments, so if you don't get
380 this right, a lot of things will not appear to work correctly with our
381 tests. If the tests fail, so do you. Fortunately, this part
382 shouldn't be too hard.
384 @node Problem 2-2 System Calls
385 @section Problem 2-2: System Calls
387 Implement the system call handler in @file{userprog/syscall.c} to
388 properly deal with all the system calls described below. Currently,
389 it ``handles'' system calls by terminating the process. You will need
390 to decipher system call arguments and take the appropriate action for
393 You are required to support the following system calls, whose syscall
394 numbers are defined in @file{lib/syscall-nr.h} and whose C functions
395 called by user programs are prototyped in @file{lib/user/syscall.h}:
399 @itemx void halt (void)
400 Stops Pintos by calling @func{power_off} (declared in
401 @file{threads/init.h}). Note that this should be seldom used, since
402 then you lose some information about possible deadlock situations,
406 @itemx void exit (int @var{status})
407 Terminates the current user program, returning @var{status} to the
408 kernel. If the process's parent @func{join}s it, this is the status
409 that will be returned. Conventionally, a @var{status} of 0 indicates
410 a successful exit. Other values may be used to indicate user-defined
411 conditions (usually errors).
414 @itemx pid_t exec (const char *@var{cmd_line})
415 Runs the executable whose name is given in @var{cmd_line}, passing any
416 given arguments, and returns the new process's program id (pid). Must
417 return pid -1, which otherwise should not be a valid program id, if
418 there is an error loading this program.
421 @itemx int join (pid_t @var{pid})
422 Joins the process @var{pid}, using the join rules from the last
423 assignment, and returns the process's exit status. If the process was
424 terminated by the kernel (i.e.@: killed due to an exception), the exit
425 status should be -1. If the process was not a child of the calling
426 process, the return value is undefined (but kernel operation must not
430 @itemx bool create (const char *@var{file}, unsigned @var{initial_size})
431 Create a new file called @var{file} initially @var{initial_size} bytes
432 in size. Returns true if successful, false otherwise.
435 @itemx bool remove (const char *@var{file})
436 Delete the file called @var{file}. Returns true if successful, false
440 @itemx int open (const char *@var{file})
441 Open the file called @var{file}. Returns a nonnegative integer handle
442 called a ``file descriptor'' (fd), or -1 if the file could not be
443 opened. All open files associated with a process should be closed
444 when the process exits or is terminated.
446 File descriptors numbered 0 and 1 are reserved for the console: fd 0
447 is standard input (@code{stdin}), fd 1 is standard output
448 (@code{stdout}). These special file descriptors are valid as system
449 call arguments only as explicitly described below.
452 @itemx int filesize (int @var{fd})
453 Returns the size, in bytes, of the file open as @var{fd}.
456 @itemx int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
457 Read @var{size} bytes from the file open as @var{fd} into
458 @var{buffer}. Returns the number of bytes actually read (0 at end of
459 file), or -1 if the file could not be read (due to a condition other
460 than end of file). Fd 0 reads from the keyboard using
464 @itemx int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
465 Write @var{size} bytes from @var{buffer} to the open file @var{fd}.
466 Returns the number of bytes actually written, or -1 if the file could
469 Fd 1 writes to the console. Your code to write to the console should
470 write all of @var{buffer} in one call to @func{putbuf}, at least as
471 long as @var{size} is not bigger than a few hundred bytes. Otherwise,
472 lines of text output by different processes may end up interleaved on
473 the console, confusing both human readers and our grading scripts.
476 @itemx void seek (int @var{fd}, unsigned @var{position})
477 Changes the next byte to be read or written in open file @var{fd} to
478 @var{position}, expressed in bytes from the beginning of the file.
479 (Thus, a @var{position} of 0 is the file's start.)
481 A seek past the current end of a file is not an error. A later read
482 obtains 0 bytes, indicating end of file. A later write extends the
483 file, filling any unwritten gap with zeros. (However, in Pintos files
484 have a fixed length until project 4 is complete, so writes past end of
485 file will return an error.) These semantics are implemented in the
486 file system and do not require any special effort in system call
490 @itemx unsigned tell (int @var{fd})
491 Returns the position of the next byte to be read or written in open
492 file @var{fd}, expressed in bytes from the beginning of the file.
495 @itemx void close (int @var{fd})
496 Close file descriptor @var{fd}.
499 The file defines other syscalls. Ignore them for now. You will
500 implement some of them in project 3 and the rest in project 4, so be
501 sure to design your system with extensibility in mind.
503 To implement syscalls, you will need to provide a way of copying data
504 from the user's virtual address space into the kernel and vice versa.
505 This can be a bit tricky: what if the user provides an invalid
506 pointer, a pointer into kernel memory, or points to a block that is
507 partially in one of those regions? You should handle these cases by
508 terminating the user process. You will need this code before you can
509 even obtain the system call number, because the system call number is
510 on the user's stack in the user's virtual address space. We recommend
511 writing and testing this code before implementing any other system
514 @anchor{Synchronizing File Access}
515 You must make sure that system calls are properly synchronized so that
516 any number of user processes can make them at once. In particular, it
517 is not safe to call into the filesystem code provided in the
518 @file{filesys} directory from multiple threads at once. For now, we
519 recommend adding a single lock that controls access to the filesystem
520 code. You should acquire this lock before calling any functions in
521 the @file{filesys} directory, and release it afterward. Don't forget
522 that @func{process_execute} also accesses files. @strong{For now, we
523 recommend against modifying code in the @file{filesys} directory.}
525 We have provided you a user-level function for each system call in
526 @file{lib/user/syscall.c}. These provide a way for user processes to
527 invoke each system call from a C program. Each uses a little inline
528 assembly code to invoke the system call and (if appropriate) returns the
529 system call's return value.
531 When you're done with this part, and forevermore, Pintos should be
532 bulletproof. Nothing that a user program can do should ever cause the
533 OS to crash, halt, assert fail, or otherwise stop running. It is
534 important to emphasize this point: our tests will try to break your
535 system calls in many, many ways. You need to think of all the corner
536 cases and handle them. The sole way a user program should be able to
537 cause the OS to halt is by invoking the @code{halt} system call.
539 If a system call is passed an invalid argument, acceptable options
540 include returning an error value (for those calls that return a
541 value), returning an undefined value, or terminating the process.
543 @xref{System Calls}, for more information on how syscalls work.
545 @node User Programs FAQ
550 @b{Do we need a working project 1 to implement project 2?}
552 You may find the code for @func{thread_join} to be useful in
553 implementing the join syscall, but besides that, you can use
554 the original code provided for project 1.
557 @b{@samp{pintos put} always panics.}
559 Here are the most common causes:
563 The disk hasn't yet been formatted (with @samp{pintos run -f}).
566 The file name specified is too long. The file system limits file names
567 to 14 characters. If you're using a command like @samp{pintos put
568 ../../tests/userprog/echo}, that overflows the limit. Use
569 @samp{pintos put ../../tests/userprog/echo echo} to put the file under
570 the name @file{echo} instead.
573 The file system is full.
576 The file system already contains 10 files. (There's a 10-file limit for
577 the base Pintos file system.)
580 The file system is so fragmented that there's not enough contiguous
585 @b{All my user programs die with page faults.}
587 This will generally happen if you haven't implemented problem 2-1
588 yet. The reason is that the basic C library for user programs tries
589 to read @var{argc} and @var{argv} off the stack. Because the stack
590 isn't properly set up yet, this causes a page fault.
593 @b{I implemented 2-1 and now all my user programs die with
594 @samp{system call!}.}
596 Every reasonable program tries to make at least one system call
597 (@func{exit}) and most programs make more than that. Notably,
598 @func{printf} invokes the @code{write} system call. The default
599 system call handler just prints @samp{system call!} and terminates the
600 program. You'll have to implement 2-2 before you see anything more
601 interesting. Until then, you can use @func{hex_dump} to convince
602 yourself that 2-1 is implemented correctly (@pxref{Argument Passing to
606 @b{Is there a way I can disassemble user programs?}
608 The @command{i386-elf-objdump} utility can disassemble entire user
609 programs or object files. Invoke it as @code{i386-elf-objdump -d
610 @var{file}}. You can also use @code{i386-elf-gdb}'s
611 @command{disassemble} command to disassemble individual functions in
612 object files compiled with debug information.
615 @b{Why can't I use many C include files in my Pintos programs?}
617 The C library we provide is very limited. It does not include many of
618 the features that are expected of a real operating system's C library.
619 The C library must be built specifically for the operating system (and
620 architecture), since it must make system calls for I/O and memory
621 allocation. (Not all functions do, of course, but usually the library
622 is compiled as a unit.)
625 @b{Can I use lib@var{foo} in my Pintos programs?}
627 The chances are good that lib@var{foo} uses parts of the C library
628 that Pintos doesn't implement. It will probably take at least some
629 porting effort to make it work under Pintos. Notably, the Pintos
630 userland C library does not have a @func{malloc} implementation.
633 @b{How do I compile new user programs?}
635 You need to modify @file{tests/Makefile}.
638 @b{What's the difference between @code{tid_t} and @code{pid_t}?}
640 A @code{tid_t} identifies a kernel thread, which may have a user
641 process running in it (if created with @func{process_execute}) or not
642 (if created with @func{thread_create}). It is a data type used only
645 A @code{pid_t} identifies a user process. It is used by user
646 processes and the kernel in the @code{exec} and @code{join} system
649 You can choose whatever suitable types you like for @code{tid_t} and
650 @code{pid_t}. By default, they're both @code{int}. You can make them
651 a one-to-one mapping, so that the same values in both identify the
652 same process, or you can use a more complex mapping. It's up to you.
655 @b{I can't seem to figure out how to read from and write to user
656 memory. What should I do?}
658 The kernel must treat user memory delicately. As part of a system
659 call, the user can pass to the kernel a null pointer, a pointer to
660 unmapped virtual memory, or a pointer to kernel virtual address space
661 (above @code{PHYS_BASE}). All of these types of invalid pointers must
662 be rejected without harm to the kernel or other running processes. At
663 your option, the kernel may handle invalid pointers by terminating the
664 process or returning from the system call with an error.
666 There are at least two reasonable ways to do this correctly. The
667 first method is to ``verify then access'':@footnote{These terms are
668 made up for this document. They are not standard terminology.} verify
669 the validity of a user-provided pointer, then dereference it. If you
670 choose this route, you'll want to look at the functions in
671 @file{userprog/pagedir.c} and in @file{threads/mmu.h}. This is the
672 simplest way to handle user memory access.
674 The second method is to ``assume and react'': directly dereference
675 user pointers, after checking that they point below @code{PHYS_BASE}.
676 Invalid user pointers will then cause a ``page fault'' that you can
677 handle by modifying the code for @func{page_fault} in
678 @file{userprog/exception.cc}. This technique is normally faster
679 because it takes advantage of the processor's MMU, so it tends to be
680 used in real kernels (including Linux).
682 In either case, you need to make sure not to ``leak'' resources. For
683 example, suppose that your system call has acquired a lock or
684 allocated a page of memory. If you encounter an invalid user pointer
685 afterward, you must still be sure to release the lock or free the page
686 of memory. If you choose to ``verify then access,'' then this should
687 be straightforward, but for ``assume and react'' it's more difficult,
688 because there's no way to return an error code from a memory access.
689 Therefore, for those who want to try the latter technique, we'll
690 provide a little bit of helpful code:
693 /* Tries to copy a byte from user address USRC to kernel address DST.
694 Returns true if successful, false if USRC is invalid. */
695 static inline bool get_user (uint8_t *dst, const uint8_t *usrc) {
697 asm ("mov %%eax, offset 1f; mov %%al, %2; mov %0, %%al; 1:"
698 : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
702 /* Tries write BYTE to user address UDST.
703 Returns true if successful, false if UDST is invalid. */
704 static inline bool put_user (uint8_t *udst, uint8_t byte) {
706 asm ("mov %%eax, offset 1f; mov %0, %b2; 1:"
707 : "=m" (*udst), "=&a" (eax) : "r" (byte));
712 Each of these functions assumes that the user address has already been
713 verified to be below @code{PHYS_BASE}. They also assume that you've
714 modified @func{page_fault} so that a page fault in the kernel causes
715 @code{eax} to be set to 0 and its former value copied into @code{eip}.
718 @b{I'm also confused about reading from and writing to the stack. Can
723 Only non-@samp{char} values will have issues when writing them to
724 memory. If a digit is in a string, it is considered a character.
725 However, the value of @code{argc} would be a non-char.
728 You will need to write characters and non-characters into main memory.
731 When you add items to the stack, you will be decrementing the stack
732 pointer. You'll need to decrement the stack pointer before writing to
736 Each character is 1 byte.
740 @b{Why doesn't keyboard input work with @samp{pintos -v}?}
742 Serial input isn't implemented. Don't use @samp{pintos -v} if you
743 want to use the shell or otherwise provide keyboard input.
747 * Problem 2-1 Argument Passing FAQ::
748 * Problem 2-2 System Calls FAQ::
751 @node Problem 2-1 Argument Passing FAQ
752 @subsection Problem 2-1: Argument Passing FAQ
756 @b{Why is the top of the stack at @t{0xc0000000}? Isn't that off the
757 top of user virtual memory? Shouldn't it be @t{0xbfffffff}?}
759 When the processor pushes data on the stack, it decrements the stack
760 pointer first. Thus, the first (4-byte) value pushed on the stack
761 will be at address @t{0xbffffffc}.
763 Also, the stack should always be aligned to a 4-byte boundary, but
764 @t{0xbfffffff} isn't.
767 @b{Is @code{PHYS_BASE} fixed?}
769 No. You should be able to support @code{PHYS_BASE} values that are
770 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xc0000000},
771 simply via recompilation.
774 @node Problem 2-2 System Calls FAQ
775 @subsection Problem 2-2: System Calls FAQ
779 @b{Can I just cast a pointer to a @struct{file} object to get a
780 unique file descriptor? Can I just cast a @code{struct thread *} to a
781 @code{pid_t}? It's so much simpler that way!}
783 This is a design decision you will have to make for yourself.
784 However, note that most operating systems do distinguish between file
785 descriptors (or pids) and the addresses of their kernel data
786 structures. You might want to give some thought as to why they do so
787 before committing yourself.
790 @b{Can I set a maximum number of open files per process?}
792 From a design standpoint, it would be better not to set an arbitrary
793 maximum. That said, if your design calls for it, you may impose a
794 limit of 128 open files per process (as the Solaris machines here do).
797 @anchor{Removing an Open File}
798 @b{What happens when two (or more) processes have a file open and one of
801 You should copy the standard Unix semantics for files. That is, when
802 a file is removed an process which has a file descriptor for that file
803 may continue to do operations on that descriptor. This means that
804 they can read and write from the file. The file will not have a name,
805 and no other processes will be able to open it, but it will continue
806 to exist until all file descriptors referring to the file are closed
807 or the machine shuts down.
810 @b{I've discovered that some of my user programs need more than one 4
811 kB page of stack space. What should I do?}
813 You may modify the stack setup code to allocate more than one page of
814 stack space for each process.
817 @node 80x86 Calling Convention
818 @section 80@var{x}86 Calling Convention
820 What follows is a quick and dirty discussion of the 80@var{x}86
821 calling convention. Some of the basics should be familiar from CS
822 107, and if you've already taken CS 143 or EE 182, then you should
823 have seen even more of it. I've omitted some of the complexity, since
824 this isn't a class in how function calls work, so don't expect this to
825 be exactly correct in full, gory detail. If you do want all the
826 details, you can refer to @bibref{SysV-i386}.
828 Whenever a function call happens, you need to put the arguments on the
829 call stack for that function, before the code for that function
830 executes, so that the callee has access to those values. The caller
831 has to be responsible for this (be sure you understand why).
832 Therefore, when you compile a program, the assembly code emitted will
833 have in it, before every function call, a bunch of instructions that
834 prepares for the call in whatever manner is conventional for the
835 machine you're working on. This includes saving registers as needed,
836 putting stuff on the stack, saving the location to return to somewhere
837 (so that when the callee finishes, it knows where the caller code is),
838 and some other bookkeeping stuff. Then you do the jump to the
839 callee's code, and it goes along, assuming that the stack and
840 registers are prepared in the appropriate manner. When the callee is
841 done, it looks at the return location as saved earlier, and jumps back
842 to that location. The caller may then have to do some cleanup:
843 clearing arguments and the return value off the stack, restoring
844 registers that were saved before the call, and so on.
846 If you think about it, some of these things should remind you of
849 As an aside, in general, function calls are not cheap. You have to do
850 a bunch of memory writes to prepare the stack, you need to save and
851 restore registers before and after a function call, you need to write
852 the stack pointer, you have a couple of jumps which probably wrecks
853 some of your caches. This is why inlining code can be much faster.
856 * Argument Passing to main::
859 @node Argument Passing to main
860 @subsection Argument Passing to @code{main()}
862 In @func{main}'s case, there is no caller to prepare the stack
863 before it runs. Therefore, the kernel needs to do it. Fortunately,
864 since there's no caller, there are no registers to save, no return
865 address to deal with, etc. The only difficult detail to take care of,
866 after loading the code, is putting the arguments to @func{main} on
869 (The above is a small lie: most compilers will emit code where main
870 isn't strictly speaking the first function. This isn't an important
871 detail. If you want to look into it more, try disassembling a program
872 and looking around a bit. However, you can just act as if
873 @func{main} is the very first function called.)
875 Pintos is written for the 80@var{x}86 architecture. Therefore, we
876 need to adhere to the 80@var{x}86 calling convention. Basically, you
877 put all the arguments on the stack and move the stack pointer
878 appropriately. You also need to insert space for the function's
879 ``return address'': even though the initial function doesn't really
880 have a caller, its stack frame must have the same layout as any other
881 function's. The program will assume that the stack has been laid out
882 this way when it begins running.
884 So, what are the arguments to @func{main}? Just two: an @samp{int}
885 (@code{argc}) and a @samp{char **} (@code{argv}). @code{argv} is an
886 array of strings, and @code{argc} is the number of strings in that
887 array. However, the hard part isn't these two things. The hard part
888 is getting all the individual strings in the right place. As we go
889 through the procedure, let us consider the following example command:
890 @samp{/bin/ls -l foo bar}.
892 The first thing to do is to break the command line into individual
893 strings: @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}. These
894 constitute the arguments of the command, including the program name
895 itself (which belongs in @code{argv[0]}).
897 These individual, null-terminated strings should be placed on the user
898 stack. They may be placed in any order, as you'll see shortly,
899 without affecting how main works, but for simplicity let's assume they
900 are in reverse order (keeping in mind that the stack grows downward on
901 an 80@var{x}86 machine). As we copy the strings onto the stack, we
902 record their (virtual) stack addresses. These addresses will become
903 important when we write the argument vector (two paragraphs down).
905 After we push all of the strings onto the stack, we adjust the stack
906 pointer so that it is word-aligned: that is, we move it down to the
907 next 4-byte boundary. This is required because we will next be
908 placing several words of data on the stack, and they must be aligned
909 to be read correctly. In our example, as you'll see below,
910 the strings start at address @t{0xffed}. One word below that would be
911 at @t{0xffe9}, so we could in theory put the next word on the stack
912 there. However, since the stack pointer should always be
913 word-aligned, we instead leave the stack pointer at @t{0xffe8}.
915 Once we align the stack pointer, we then push the elements of the
916 argument vector, that is, a null pointer, then the addresses of the
917 strings @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}) onto
918 the stack. This must be done in reverse order, such that
919 @code{argv[0]} is at the lowest virtual address, again because the
920 stack is growing downward. (The null pointer pushed first is because
921 @code{argv[argc]} must be a null pointer.) This is because we are now
922 writing the actual array of strings; if we write them in the wrong
923 order, then the strings will be in the wrong order in the array. This
924 is also why, strictly speaking, it doesn't matter what order the
925 strings themselves are placed on the stack: as long as the pointers
926 are in the right order, the strings themselves can really be anywhere.
927 After we finish, we note the stack address of the first element of the
928 argument vector, which is @code{argv} itself.
930 Then we push @code{argv} (that is, the address of the first element of
931 the @code{argv} array) onto the stack, along with the length of the
932 argument vector (@code{argc}, 4 in this example). This must also be
933 done in this order, since @code{argc} is the first argument to
934 @func{main} and therefore is on first (smaller address) on the
935 stack. Finally, we push a fake ``return address'' and leave the stack
936 pointer to point to its location.
938 All this may sound very confusing, so here's a picture which will
939 hopefully clarify what's going on. This represents the state of the
940 stack and the relevant registers right before the beginning of the
941 user program (assuming for this example that the stack bottom is
947 @multitable {@t{0xbfffffff}} {``return address''} {@t{/bin/ls\0}}
948 @item Address @tab Name @tab Data
949 @item @t{0xbffffffc} @tab @code{*argv[3]} @tab @samp{bar\0}
950 @item @t{0xbffffff8} @tab @code{*argv[2]} @tab @samp{foo\0}
951 @item @t{0xbffffff5} @tab @code{*argv[1]} @tab @samp{-l\0}
952 @item @t{0xbfffffed} @tab @code{*argv[0]} @tab @samp{/bin/ls\0}
953 @item @t{0xbfffffec} @tab word-align @tab @samp{\0}
954 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0}
955 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc}
956 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8}
957 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5}
958 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed}
959 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8}
960 @item @t{0xbfffffd0} @tab @code{argc} @tab 4
961 @item @t{0xbfffffcc} @tab ``return address'' @tab 0
967 In this example, the stack pointer would be initialized to
970 As shown above, your code should start the stack at the very top of
971 the user virtual address space, in the page just below virtual address
972 @code{PHYS_BASE} (defined in @file{threads/mmu.h}).
974 You may find the non-standard @func{hex_dump} function, declared in
975 @file{<stdio.h>}, useful for debugging your argument passing code.
976 Here's what it would show in the above example, given that
977 @code{PHYS_BASE} is @t{0xc0000000}:
980 bfffffc0 00 00 00 00 | ....|
981 bfffffd0 04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
982 bfffffe0 f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
983 bffffff0 6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
987 @section System Calls
989 We have already been dealing with one way that the operating system
990 can regain control from a user program: interrupts from timers and I/O
991 devices. These are ``external'' interrupts, because they are caused
992 by entities outside the CPU.
994 The operating system is also called to deal with software exceptions,
995 which are events generated in response to the code. These can be
996 errors such as a page fault or division by zero. However, exceptions
997 are also the means by which a user program can request services
998 (``system calls'') from the operating system.
1000 In the 80@var{x}86 architecture, the @samp{int} instruction is the
1001 most commonly used means for invoking system calls. This instruction
1002 is handled in the same way as other software exceptions. In Pintos,
1003 user programs invoke @samp{int $0x30} to make a system call. The
1004 system call number and any additional arguments are expected to be
1005 pushed on the stack in the normal fashion before invoking the
1008 The normal calling convention pushes function arguments on the stack
1009 from right to left and the stack grows downward. Thus, when the
1010 system call handler @func{syscall_handler} gets control, the system
1011 call number is in the 32-bit word at the caller's stack pointer, the
1012 first argument is in the 32-bit word at the next higher address, and
1013 so on. The caller's stack pointer is accessible to
1014 @func{syscall_handler} as the @samp{esp} member of the @code{struct
1015 intr_frame} passed to it.
1017 Here's an example stack frame for calling a system call numbered 10
1018 with three arguments passed as 1, 2, and 3. The stack addresses are
1024 @multitable {@t{0xbffffe7c}} {Value}
1025 @item Address @tab Value
1026 @item @t{0xbffffe7c} @tab 3
1027 @item @t{0xbffffe78} @tab 2
1028 @item @t{0xbffffe74} @tab 1
1029 @item @t{0xbffffe70} @tab 10
1035 In this example, the caller's stack pointer would be at
1038 The 80@var{x}86 convention for function return values is to place them
1039 in the @samp{EAX} register. System calls that return a value can do
1040 so by modifying the @samp{eax} member of @struct{intr_frame}.
1042 You should try to avoid writing large amounts of repetitive code for
1043 implementing system calls. Each system call argument, whether an
1044 integer or a pointer, takes up 4 bytes on the stack. You should be able
1045 to take advantage of this to avoid writing much near-identical code for
1046 retrieving each system call's arguments from the stack.