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. Your submission
19 should define @code{THREAD_JOIN_IMPLEMENTED} in @file{constants.h}
20 (@pxref{Conditional Compilation}).
22 Up to now, all of the code you have written for Pintos has been part
23 of the operating system kernel. This means, for example, that all the
24 test code from the last assignment ran as part of the kernel, with
25 full access to privileged parts of the system. Once we start running
26 user programs on top of the operating system, this is no longer true.
27 This project deals with consequences of the change.
29 We allow more than one user program to run at a time. Because user
30 programs are written and compiled to work under the illusion that they
31 have the entire machine, when you load into memory and run more than
32 one process at a time, you must manage things correctly to maintain
35 Before we delve into the details of the new code that you'll be
36 working with, you should probably undo the test cases from project 1.
40 * Using the File System::
41 * How User Programs Work::
42 * Virtual Memory Layout::
43 * Global Requirements::
44 * Problem 2-1 Argument Passing::
45 * Problem 2-2 System Calls::
47 * 80x86 Calling Convention::
54 The easiest way to get an overview of the programming you will be
55 doing is to simply go over each part you'll be working with. In
56 @file{userprog}, you'll find a small number of files, but here is
57 where the bulk of your work will be:
62 Loads ELF binaries and starts processes.
66 A simple manager for 80@var{x} page directories and page tables.
67 Although you probably won't want to modify this code for this project,
68 you may want to call some of its functions. In particular,
69 @func{pagedir_get_page} may be helpful for accessing user memory.
73 Whenever a user process wants to access some kernel functionality, it
74 needs to do so via a system call. This is a skeleton system call
75 handler. Currently, it just prints a message and terminates the user
76 process. In part 2 of this project you will add code to do everything
77 else needed by system calls.
81 When a user process performs a privileged or prohibited operation, it
82 traps into the kernel as an ``exception'' or ``fault.''@footnote{We
83 will treat these terms as synonymous. There is no standard
84 distinction between them, although the Intel processor manuals define
85 them slightly differently on 80@var{x}86.} These files handle
86 exceptions. Currently all exceptions simply print a message and
87 terminate the process. Some, but not all, solutions to project 2
88 require modifying @func{page_fault} in this file.
92 The 80@var{x}86 is a segmented architecture. The Global Descriptor
93 Table (GDT) is a table that describes the segments in use. These
94 files set up the GDT. @strong{You should not need to modify these
95 files for any of the projects.} However, you can read the code if
96 you're interested in how the GDT works.
100 The Task-State Segment (TSS) is used for 80@var{x}86 architectural
101 task switching. Pintos uses the TSS only for switching stacks when a
102 user process enters an interrupt handler, as does Linux. @strong{You
103 should not need to modify these files for any of the projects.}
104 However, you can read the code if you're interested in how the TSS
108 Finally, in @file{lib/kernel}, you might want to use
109 @file{bitmap.[ch]}. A bitmap is basically an array of bits, each of
110 which can be true or false. Bitmaps are typically used to keep track
111 of the usage of a large array of (identical) resources: if resource
112 @var{n} is in use, then bit @var{n} of the bitmap is true. You might
113 find it useful for tracking memory pages, for example.
115 @node Using the File System
116 @section Using the File System
118 You will need to use some file system code for this project. First,
119 user programs are loaded from the file system. Second, many of the
120 system calls you must implement deal with the file system. However,
121 the focus of this project is not on the file system code, so we have
122 provided a simple file system in the @file{filesys} directory. You
123 will want to look over the @file{filesys.h} and @file{file.h}
124 interfaces to understand how to use the file system, and especially
125 its many limitations. @strong{You should not modify the file system
126 code for this project}. Proper use of the file system routines now
127 will make life much easier for project 4, when you improve the file
128 system implementation.
130 You need to be able to create and format simulated disks. The
131 @command{pintos} program provides this functionality with its
132 @option{make-disk} command. From the @file{userprog/build} directory,
133 execute @code{pintos make-disk fs.dsk 2}. This command creates a 2 MB
134 simulated disk named @file{fs.dsk}. (It does not actually start
135 Pintos.) Then format the disk by passing the @option{-f} option to
136 Pintos on the kernel's command line: @code{pintos run -f}.
138 You'll need a way to get files in and out of the simulated file
139 system. The @code{pintos} @option{put} and @option{get} commands are
140 designed for this. To copy @file{@var{file}} into the Pintos file
141 system, use the command @file{pintos put @var{file}}. To copy it to
142 the Pintos file system under the name @file{@var{newname}}, add the
143 new name to the end of the command: @file{pintos put @var{file}
144 @var{newname}}. The commands for copying files out of a VM are
145 similar, but substitute @option{get} for @option{get}.
147 Incidentally, these commands work by passing special options
148 @option{-ci} and @option{-co} on the kernel's command line and copying
149 to and from a special simulated disk named @file{scratch.dsk}. If
150 you're very curious, you can look at the @command{pintos} program as
151 well as @file{filesys/fsutil.c} to learn the implementation details,
152 but it's really not relevant for this project.
154 You can delete a file from the Pintos file system using the @option{-r
155 @var{file}} kernel option, e.g.@: @code{pintos run -r @var{file}}.
156 Also, @option{-ls} lists the files in the file system and @option{-p
157 @var{file}} prints a file's contents to the display.
159 @node How User Programs Work
160 @section How User Programs Work
162 Pintos can run normal C programs. In fact, it can run any program you
163 want, provided it's compiled into the proper file format, and uses
164 only the system calls you implement. (For example, @func{malloc}
165 makes use of functionality that isn't provided by any of the syscalls
166 we require you to support.) The only other limitation is that Pintos
167 can't run programs using floating point operations, since it doesn't
168 include the necessary kernel functionality to save and restore the
169 processor's floating-point unit when switching threads. You can look
170 in @file{tests/userprog} directory for some examples.
172 Pintos loads ELF executables, where ELF is an executable format used
173 by Linux, Solaris, and many other Unix and Unix-like systems.
174 Therefore, you can use any compiler and linker that produce
175 80@var{x}86 ELF executables to produce programs for Pintos. We
176 recommend using the tools we provide in the @file{tests/userprog}
177 directory. By default, the @file{Makefile} in this directory will
178 compile the test programs we provide. You can edit the
179 @file{Makefile} to compile your own test programs as well.
181 One thing you should realize immediately is that, until you use the
182 above operation to copy a test program to the emulated disk, Pintos
183 will be unable to do very much useful work. You will also find that
184 you won't be able to do interesting things until you copy a variety of
185 programs to the disk. A useful technique is to create a clean
186 reference disk and copy that over whenever you trash your
187 @file{fs.dsk} beyond a useful state, which may happen occasionally
190 @node Virtual Memory Layout
191 @section Virtual Memory Layout
193 Virtual memory in Pintos is divided into two regions: user virtual
194 memory and kernel virtual memory. User virtual memory ranges from
195 virtual address 0 up to @code{PHYS_BASE}, which is defined in
196 @file{threads/mmu.h} and defaults to @t{0xc0000000} (3 GB). Kernel
197 virtual memory occupies the rest of the virtual address space, from
198 @code{PHYS_BASE} up to 4 GB.
200 User virtual memory is per-process. Conceptually, each process is
201 free to use the entire space of user virtual memory however it
202 chooses. When the kernel switches from one process to another, it
203 also switches user virtual address spaces by switching the processor's
204 page directory base register (see @func{pagedir_activate in
205 @file{userprog/pagedir.c}}.
207 Kernel virtual memory is global. It is always mapped the same way,
208 regardless of what user process or kernel thread is running. In
209 Pintos, kernel virtual memory is mapped one-to-one to physical
210 memory. That is, virtual address @code{PHYS_ADDR} accesses physical
211 address 0, virtual address @code{PHYS_ADDR} + @t{0x1234} access
212 physical address @t{0x1234}, and so on up to the size of the machine's
215 User programs can only access user virtual memory. An attempt to
216 access kernel virtual memory will cause a page fault, handled by
217 @func{page_fault} in @file{userprog/exception.c}, and the process
218 will be terminated. Kernel threads can access both kernel virtual
219 memory and, if a user process is running, the user virtual memory of
220 the running process. However, even in the kernel, an attempt to
221 access memory at a user virtual address that doesn't have a page
222 mapped into it will cause a page fault.
224 @node Global Requirements
225 @section Global Requirements
227 For testing and grading purposes, we have some simple requirements for
232 The kernel should print out the program's name and exit status
233 whenever a process exits, e.g.@: @code{shell: exit(-1)}. The name
234 printed should be the full name passed to @func{process_execute},
235 except that it is acceptable to truncate it to 15 characters to allow
236 for the limited space in @struct{thread}.
239 Aside from this, the kernel should print out no other messages that
240 Pintos as provided doesn't already print. You
241 may understand all those debug messages, but we won't, and it just
242 clutters our ability to see the stuff we care about.
245 Additionally, while it may be useful to hard-code which process will
246 run at startup while debugging, before you submit your code you must
247 make sure that it takes the start-up process name and arguments from
248 the @samp{-ex} argument. For example, running @code{pintos run -ex
249 "testprogram 1 2 3 4"} will spawn @samp{testprogram 1 2 3 4} as the
253 @node Problem 2-1 Argument Passing
254 @section Problem 2-1: Argument Passing
256 Currently, @func{process_execute} does not support passing arguments
257 to new processes. UNIX and other operating systems do allow passing
258 command line arguments to a program, which accesses them via the argc,
259 argv arguments to main. You must implement this functionality by
260 extending @func{process_execute} so that instead of simply taking a
261 program file name as its argument, it divides it into words at spaces.
262 The first word is the program name, the second word is the first
263 argument, and so on. That is, @code{process_execute("grep foo bar")}
264 should run @program{grep} passing two arguments @code{foo} and
265 @file{bar}. A few details:
269 Multiple spaces are considered the same as a single space, so that
270 @code{process_execute("grep foo bar")} would be equivalent to our
274 You can impose a reasonable limit on the length of the command line
275 arguments. For example, you could limit the arguments to those that
276 will fit in a single page (4 kB).
279 You can parse the argument strings any way you like. If you're lost,
280 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
281 implemented with thorough comments in @file{lib/string.c}. You can
282 find more about it by looking at the man page (run @code{man strtok_r}
286 @xref{80x86 Calling Convention}, for information on exactly how you
287 need to set up the stack.
290 @strong{This functionality is extremely important.} Almost all our
291 test cases rely on being able to pass arguments, so if you don't get
292 this right, a lot of things will not appear to work correctly with our
293 tests. If the tests fail, so do you. Fortunately, this part
294 shouldn't be too hard.
296 @node Problem 2-2 System Calls
297 @section Problem 2-2: System Calls
299 Implement the system call handler in @file{userprog/syscall.c} to
300 properly deal with all the system calls described below. Currently,
301 it ``handles'' system calls by terminating the process. You will need
302 to decipher system call arguments and take the appropriate action for
305 You are required to support the following system calls, whose syscall
306 numbers are defined in @file{lib/syscall-nr.h} and whose C functions
307 called by user programs are prototyped in @file{lib/user/syscall.h}:
311 @itemx void halt (void)
312 Stops Pintos by calling @func{power_off} (declared in
313 @file{threads/init.h}). Note that this should be seldom used, since
314 then you lose some information about possible deadlock situations,
318 @itemx void exit (int @var{status})
319 Terminates the current user program, returning @var{status} to the
320 kernel. If the process's parent @func{join}s it, this is the status
321 that will be returned. Conventionally, a @var{status} of 0 indicates
322 a successful exit. Other values may be used to indicate user-defined
323 conditions (usually errors).
326 @itemx pid_t exec (const char *@var{file})
327 Run the executable in @var{file} and return the new process's program
328 id (pid). If there is an error loading this program, returns pid -1,
329 which otherwise should not be a valid id number.
332 @itemx int join (pid_t @var{pid})
333 Joins the process @var{pid}, using the join rules from the last
334 assignment, and returns the process's exit status. If the process was
335 terminated by the kernel (i.e.@: killed due to an exception), the exit
336 status should be -1. If the process was not a child of the calling
337 process, the return value is undefined (but kernel operation must not
341 @itemx bool create (const char *@var{file}, unsigned @var{initial_size})
342 Create a new file called @var{file} initially @var{initial_size} bytes
343 in size. Returns -1 if failed, 0 if OK.
346 @itemx bool remove (const char *@var{file})
347 Delete the file called @var{file}. Returns -1 if failed, 0 if OK.
350 @itemx int open (const char *@var{file})
351 Open the file called @var{file}. Returns a nonnegative integer handle
352 called a ``file descriptor'' (fd), or -1 if the file could not be
353 opened. All open files associated with a process should be closed
354 when the process exits or is terminated.
356 File descriptors numbered 0 and 1 are reserved for the console: fd 0
357 is standard input (@code{stdin}), fd 1 is standard output
358 (@code{stdout}). These special file descriptors are valid as system
359 call arguments only as explicitly described below.
362 @itemx int filesize (int @var{fd})
363 Returns the size, in bytes, of the file open as @var{fd}.
366 @itemx int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
367 Read @var{size} bytes from the file open as @var{fd} into
368 @var{buffer}. Returns the number of bytes actually read, or -1 if the
369 file could not be read. Fd 0 reads from the keyboard using
373 @itemx int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
374 Write @var{size} bytes from @var{buffer} to the open file @var{fd}.
375 Returns the number of bytes actually written, or -1 if the file could
376 not be written. Fd 1 writes to the console.
379 @itemx void seek (int @var{fd}, unsigned @var{position})
380 Changes the next byte to be read or written in open file @var{fd} to
381 @var{position}, expressed in bytes from the beginning of the file.
382 (Thus, a @var{position} of 0 is the file's start.)
385 @itemx unsigned tell (int @var{fd})
386 Returns the position of the next byte to be read or written in open
387 file @var{fd}, expressed in bytes from the beginning of the file.
390 @itemx void close (int @var{fd})
391 Close file descriptor @var{fd}.
394 The file defines other syscalls. Ignore them for now. You will
395 implement some of them in project 3 and the rest in project 4, so be
396 sure to design your system with extensibility in mind.
398 To implement syscalls, you will need to provide a way of copying data
399 from the user's virtual address space into the kernel and vice versa.
400 This can be a bit tricky: what if the user provides an invalid
401 pointer, a pointer into kernel memory, or points to a block that is
402 partially in one of those regions? You should handle these cases by
403 terminating the user process. You will need this code before you can
404 even obtain the system call number, because the system call number is
405 on the user's stack in the user's virtual address space. We recommend
406 writing and testing this code before implementing any other system
409 You must make sure that system calls are properly synchronized so that
410 any number of user processes can make them at once. In particular, it
411 is not safe to call into the filesystem code provided in the
412 @file{filesys} directory from multiple threads at once. For now, we
413 recommend adding a single lock that controls access to the filesystem
414 code. You should acquire this lock before calling any functions in
415 the @file{filesys} directory, and release it afterward. Don't forget
416 that @func{process_execute} also accesses files. @strong{For now, we
417 recommend against modifying code in the @file{filesys} directory.}
419 We have provided you a function for each system call in
420 @file{lib/user/syscall.c}. These provide a way for user processes to
421 invoke each system call from a C program. Each of them calls an
422 assembly language routine in @file{lib/user/syscall-stub.S}, which in
423 turn invokes the system call interrupt and returns.
425 When you're done with this part, and forevermore, Pintos should be
426 bulletproof. Nothing that a user program can do should ever cause the
427 OS to crash, halt, assert fail, or otherwise stop running. The sole
428 exception is a call to the @code{halt} system call.
430 If a system call is passed an invalid argument, acceptable options
431 include returning an error value (for those calls that return a
432 value), returning an undefined value, or terminating the process.
434 @xref{System Calls}, for more information on how syscalls work.
436 @node User Programs FAQ
441 @b{Do we need a working project 1 to implement project 2?}
443 You may find the code for @func{thread_join} to be useful in
444 implementing the join syscall, but besides that, you can use
445 the original code provided for project 1.
448 @b{@samp{pintos put} always panics.}
450 Here are the most common causes:
454 The disk hasn't yet been formatted (with @samp{pintos run -f}).
457 The filename specified is too long. The file system limits file names
458 to 14 characters. If you're using a command like @samp{pintos put
459 ../../tests/userprog/echo}, that overflows the limit. Use
460 @samp{pintos put ../../tests/userprog/echo echo} to put the file under
461 the name @file{echo} instead.
464 The file is too big. The file system has a 63 kB limit.
468 @b{All my user programs die with page faults.}
470 This will generally happen if you haven't implemented problem 2-1
471 yet. The reason is that the basic C library for user programs tries
472 to read @var{argc} and @var{argv} off the stack. Because the stack
473 isn't properly set up yet, this causes a page fault.
476 @b{I implemented 2-1 and now all my user programs die with
477 @samp{system call!}.}
480 @b{Is there a way I can disassemble user programs?}
482 The @command{i386-elf-objdump} utility can disassemble entire user
483 programs or object files. Invoke it as @code{i386-elf-objdump -d
484 @var{file}}. You can also use @code{i386-elf-gdb}'s
485 @command{disassemble} command to disassemble individual functions in
486 object files compiled with debug information.
489 @b{Why can't I use many C include files in my Pintos programs?}
491 The C library we provide is very limited. It does not include many of
492 the features that are expected of a real operating system's C library.
493 The C library must be built specifically for the operating system (and
494 architecture), since it must make system calls for I/O and memory
495 allocation. (Not all functions do, of course, but usually the library
496 is compiled as a unit.)
499 @b{Can I use lib@var{foo} in my Pintos programs?}
501 The chances are good that lib@var{foo} uses parts of the C library
502 that Pintos doesn't implement. It will probably take at least some
503 porting effort to make it work under Pintos. Notably, the Pintos
504 userland C library does not have a @func{malloc} implementation.
507 @b{How do I compile new user programs?}
509 You need to modify @file{tests/Makefile}.
512 @b{What's the difference between @code{tid_t} and @code{pid_t}?}
514 A @code{tid_t} identifies a kernel thread, which may have a user
515 process running in it (if created with @func{process_execute}) or not
516 (if created with @func{thread_create}). It is a data type used only
519 A @code{pid_t} identifies a user process. It is used by user
520 processes and the kernel in the @code{exec} and @code{join} system
523 You can choose whatever suitable types you like for @code{tid_t} and
524 @code{pid_t}. By default, they're both @code{int}. You can make them
525 a one-to-one mapping, so that the same values in both identify the
526 same process, or you can use a more complex mapping. It's up to you.
529 @b{I can't seem to figure out how to read from and write to user
530 memory. What should I do?}
532 The kernel must treat user memory delicately. As part of a system
533 call, the user can pass to the kernel a null pointer, a pointer to
534 unmapped virtual memory, or a pointer to kernel virtual address space
535 (above @code{PHYS_BASE}). All of these types of invalid pointers must
536 be rejected without harm to the kernel or other running processes. At
537 your option, the kernel may handle invalid pointers by terminating the
538 process or returning from the system call with an error.
540 There are at least two reasonable ways to do this correctly. The
541 first method is to ``verify then access'':@footnote{These terms are
542 made up for this document. They are not standard terminology.} verify
543 the validity of a user-provided pointer, then dereference it. If you
544 choose this route, you'll want to look at the functions in
545 @file{userprog/pagedir.c} and in @file{threads/mmu.h}. This is the
546 simplest way to handle user memory access.
548 The second method is to ``assume and react'': directly dereference
549 user pointers, after checking that they point below @code{PHYS_BASE}.
550 Invalid user pointers will then cause a ``page fault'' that you can
551 handle by modifying the code for @func{page_fault} in
552 @file{userprog/exception.cc}. This technique is normally faster
553 because it takes advantage of the processor's MMU, so it tends to be
554 used in real kernels (including Linux).
556 In either case, you need to make sure not to ``leak'' resources. For
557 example, suppose that your system call has acquired a lock or
558 allocated a page of memory. If you encounter an invalid user pointer
559 afterward, you must still be sure to release the lock or free the page
560 of memory. If you choose to ``verify then access,'' then this should
561 be straightforward, but for ``assume and react'' it's more difficult,
562 because there's no way to return an error code from a memory access.
563 Therefore, for those who want to try the latter technique, we'll
564 provide a little bit of helpful code:
567 /* Tries to copy a byte from user address USRC to kernel address DST.
568 Returns true if successful, false if USRC is invalid. */
569 static inline bool get_user (uint8_t *dst, const uint8_t *usrc) {
571 asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
572 : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
576 /* Tries write BYTE to user address UDST.
577 Returns true if successful, false if UDST is invalid. */
578 static inline bool put_user (uint8_t *udst, uint8_t byte) {
580 asm ("movl $1f, %%eax; movb %b2, %0; 1:"
581 : "=m" (*udst), "=&a" (eax) : "r" (byte));
586 Each of these functions assumes that the user address has already been
587 verified to be below @code{PHYS_BASE}. They also assume that you've
588 modified @func{page_fault} so that a page fault in the kernel causes
589 @code{eax} to be set to 0 and its former value copied into @code{eip}.
592 @b{I'm also confused about reading from and writing to the stack. Can
597 Only non-@samp{char} values will have issues when writing them to
598 memory. If a digit is in a string, it is considered a character.
599 However, the value of @code{argc} would be a non-char.
602 You will need to write characters and non-characters into main memory.
605 When you add items to the stack, you will be decrementing the stack
606 pointer. You'll need to decrement the stack pointer before writing to
610 Each character is 1 byte.
614 @b{Why doesn't keyboard input work with @option{-v}?}
616 Serial input isn't implemented. Don't use @option{-v} if you want to
617 use the shell or otherwise type at the keyboard.
621 * Problem 2-1 Argument Passing FAQ::
622 * Problem 2-2 System Calls FAQ::
625 @node Problem 2-1 Argument Passing FAQ
626 @subsection Problem 2-1: Argument Passing FAQ
630 @b{Why is the top of the stack at @t{0xc0000000}? Isn't that off the
631 top of user virtual memory? Shouldn't it be @t{0xbfffffff}?}
633 When the processor pushes data on the stack, it decrements the stack
634 pointer first. Thus, the first (4-byte) value pushed on the stack
635 will be at address @t{0xbffffffc}.
637 Also, the stack should always be aligned to a 4-byte boundary, but
638 @t{0xbfffffff} isn't.
641 @b{Is @code{PHYS_BASE} fixed?}
643 No. You should be able to support @code{PHYS_BASE} values that are
644 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xc0000000},
645 simply via recompilation.
648 @node Problem 2-2 System Calls FAQ
649 @subsection Problem 2-2: System Calls FAQ
653 @b{Can I just cast a pointer to a @struct{file} object to get a
654 unique file descriptor? Can I just cast a @code{struct thread *} to a
655 @code{pid_t}? It's so much simpler that way!}
657 This is a design decision you will have to make for yourself.
658 However, note that most operating systems do distinguish between file
659 descriptors (or pids) and the addresses of their kernel data
660 structures. You might want to give some thought as to why they do so
661 before committing yourself.
664 @b{Can I set a maximum number of open files per process?}
666 From a design standpoint, it would be better not to set an arbitrary
667 maximum. That said, if your design calls for it, you may impose a
668 limit of 128 open files per process (as the Solaris machines here do).
671 @anchor{Removing an Open File}
672 @b{What happens when two (or more) processes have a file open and one of
675 You should copy the standard Unix semantics for files. That is, when
676 a file is removed an process which has a file descriptor for that file
677 may continue to do operations on that descriptor. This means that
678 they can read and write from the file. The file will not have a name,
679 and no other processes will be able to open it, but it will continue
680 to exist until all file descriptors referring to the file are closed
681 or the machine shuts down.
684 @b{I've discovered that some of my user programs need more than one 4
685 kB page of stack space. What should I do?}
687 You may modify the stack setup code to allocate more than one page of
688 stack space for each process.
691 @node 80x86 Calling Convention
692 @section 80@var{x}86 Calling Convention
694 What follows is a quick and dirty discussion of the 80@var{x}86
695 calling convention. Some of the basics should be familiar from CS
696 107, and if you've already taken CS 143 or EE 182, then you should
697 have seen even more of it. I've omitted some of the complexity, since
698 this isn't a class in how function calls work, so don't expect this to
699 be exactly correct in full, gory detail. If you do want all the
700 details, you can refer to @bibref{SysV-i386}.
702 Whenever a function call happens, you need to put the arguments on the
703 call stack for that function, before the code for that function
704 executes, so that the callee has access to those values. The caller
705 has to be responsible for this (be sure you understand why).
706 Therefore, when you compile a program, the assembly code emitted will
707 have in it, before every function call, a bunch of instructions that
708 prepares for the call in whatever manner is conventional for the
709 machine you're working on. This includes saving registers as needed,
710 putting stuff on the stack, saving the location to return to somewhere
711 (so that when the callee finishes, it knows where the caller code is),
712 and some other bookkeeping stuff. Then you do the jump to the
713 callee's code, and it goes along, assuming that the stack and
714 registers are prepared in the appropriate manner. When the callee is
715 done, it looks at the return location as saved earlier, and jumps back
716 to that location. The caller may then have to do some cleanup:
717 clearing arguments and the return value off the stack, restoring
718 registers that were saved before the call, and so on.
720 If you think about it, some of these things should remind you of
723 As an aside, in general, function calls are not cheap. You have to do
724 a bunch of memory writes to prepare the stack, you need to save and
725 restore registers before and after a function call, you need to write
726 the stack pointer, you have a couple of jumps which probably wrecks
727 some of your caches. This is why inlining code can be much faster.
730 * Argument Passing to main::
733 @node Argument Passing to main
734 @subsection Argument Passing to @code{main()}
736 In @func{main}'s case, there is no caller to prepare the stack
737 before it runs. Therefore, the kernel needs to do it. Fortunately,
738 since there's no caller, there are no registers to save, no return
739 address to deal with, etc. The only difficult detail to take care of,
740 after loading the code, is putting the arguments to @func{main} on
743 (The above is a small lie: most compilers will emit code where main
744 isn't strictly speaking the first function. This isn't an important
745 detail. If you want to look into it more, try disassembling a program
746 and looking around a bit. However, you can just act as if
747 @func{main} is the very first function called.)
749 Pintos is written for the 80@var{x}86 architecture. Therefore, we
750 need to adhere to the 80@var{x}86 calling convention. Basically, you
751 put all the arguments on the stack and move the stack pointer
752 appropriately. You also need to insert space for the function's
753 ``return address'': even though the initial function doesn't really
754 have a caller, its stack frame must have the same layout as any other
755 function's. The program will assume that the stack has been laid out
756 this way when it begins running.
758 So, what are the arguments to @func{main}? Just two: an @samp{int}
759 (@code{argc}) and a @samp{char **} (@code{argv}). @code{argv} is an
760 array of strings, and @code{argc} is the number of strings in that
761 array. However, the hard part isn't these two things. The hard part
762 is getting all the individual strings in the right place. As we go
763 through the procedure, let us consider the following example command:
764 @samp{/bin/ls -l foo bar}.
766 The first thing to do is to break the command line into individual
767 strings: @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}. These
768 constitute the arguments of the command, including the program name
769 itself (which belongs in @code{argv[0]}).
771 These individual, null-terminated strings should be placed on the user
772 stack. They may be placed in any order, as you'll see shortly,
773 without affecting how main works, but for simplicity let's assume they
774 are in reverse order (keeping in mind that the stack grows downward on
775 an 80@var{x}86 machine). As we copy the strings onto the stack, we
776 record their (virtual) stack addresses. These addresses will become
777 important when we write the argument vector (two paragraphs down).
779 After we push all of the strings onto the stack, we adjust the stack
780 pointer so that it is word-aligned: that is, we move it down to the
781 next 4-byte boundary. This is required because we will next be
782 placing several words of data on the stack, and they must be aligned
783 in order to be read correctly. In our example, as you'll see below,
784 the strings start at address @t{0xffed}. One word below that would be
785 at @t{0xffe9}, so we could in theory put the next word on the stack
786 there. However, since the stack pointer should always be
787 word-aligned, we instead leave the stack pointer at @t{0xffe8}.
789 Once we align the stack pointer, we then push the elements of the
790 argument vector, that is, a null pointer, then the addresses of the
791 strings @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}) onto
792 the stack. This must be done in reverse order, such that
793 @code{argv[0]} is at the lowest virtual address, again because the
794 stack is growing downward. (The null pointer pushed first is because
795 @code{argv[argc]} must be a null pointer.) This is because we are now
796 writing the actual array of strings; if we write them in the wrong
797 order, then the strings will be in the wrong order in the array. This
798 is also why, strictly speaking, it doesn't matter what order the
799 strings themselves are placed on the stack: as long as the pointers
800 are in the right order, the strings themselves can really be anywhere.
801 After we finish, we note the stack address of the first element of the
802 argument vector, which is @code{argv} itself.
804 Then we push @code{argv} (that is, the address of the first element of
805 the @code{argv} array) onto the stack, along with the length of the
806 argument vector (@code{argc}, 4 in this example). This must also be
807 done in this order, since @code{argc} is the first argument to
808 @func{main} and therefore is on first (smaller address) on the
809 stack. Finally, we push a fake ``return address'' and leave the stack
810 pointer to point to its location.
812 All this may sound very confusing, so here's a picture which will
813 hopefully clarify what's going on. This represents the state of the
814 stack and the relevant registers right before the beginning of the
815 user program (assuming for this example that the stack bottom is
821 @multitable {@t{0xbfffffff}} {``return address''} {@t{/bin/ls\0}}
822 @item Address @tab Name @tab Data
823 @item @t{0xbffffffc} @tab @code{*argv[3]} @tab @samp{bar\0}
824 @item @t{0xbffffff8} @tab @code{*argv[2]} @tab @samp{foo\0}
825 @item @t{0xbffffff5} @tab @code{*argv[1]} @tab @samp{-l\0}
826 @item @t{0xbfffffed} @tab @code{*argv[0]} @tab @samp{/bin/ls\0}
827 @item @t{0xbfffffec} @tab word-align @tab @samp{\0}
828 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0}
829 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc}
830 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8}
831 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5}
832 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed}
833 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8}
834 @item @t{0xbfffffd0} @tab @code{argc} @tab 4
835 @item @t{0xbfffffcc} @tab ``return address'' @tab 0
841 In this example, the stack pointer would be initialized to
844 As shown above, your code should start the stack at the very top of
845 the user virtual address space, in the page just below virtual address
846 @code{PHYS_BASE} (defined in @file{threads/mmu.h}).
848 You may find the non-standard @func{hex_dump} function, declared in
849 @file{<stdio.h>}, useful for debugging your argument passing code.
850 Here's what it would show in the above example, given that
851 @code{PHYS_BASE} is @t{0xc0000000}:
854 bfffffc0 00 00 00 00 | ....|
855 bfffffd0 04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
856 bfffffe0 f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
857 bffffff0 6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
861 @section System Calls
863 We have already been dealing with one way that the operating system
864 can regain control from a user program: interrupts from timers and I/O
865 devices. These are ``external'' interrupts, because they are caused
866 by entities outside the CPU.
868 The operating system is also called to deal with software exceptions,
869 which are events generated in response to the code. These can be
870 errors such as a page fault or division by zero. However, exceptions
871 are also the means by which a user program can request services
872 (``system calls'') from the operating system.
874 In the 80@var{x}86 architecture, the @samp{int} instruction is the
875 most commonly used means for invoking system calls. This instruction
876 is handled in the same way as other software exceptions. In Pintos,
877 user programs invoke @samp{int $0x30} to make a system call. The
878 system call number and any additional arguments are expected to be
879 pushed on the stack in the normal fashion before invoking the
882 The normal calling convention pushes function arguments on the stack
883 from right to left and the stack grows downward. Thus, when the
884 system call handler @func{syscall_handler} gets control, the system
885 call number is in the 32-bit word at the caller's stack pointer, the
886 first argument is in the 32-bit word at the next higher address, and
887 so on. The caller's stack pointer is accessible to
888 @func{syscall_handler} as the @samp{esp} member of the @code{struct
889 intr_frame} passed to it.
891 Here's an example stack frame for calling a system call numbered 10
892 with three arguments passed as 1, 2, and 3. The stack addresses are
898 @multitable {@t{0xbffffe7c}} {Value}
899 @item Address @tab Value
900 @item @t{0xbffffe7c} @tab 3
901 @item @t{0xbffffe78} @tab 2
902 @item @t{0xbffffe74} @tab 1
903 @item @t{0xbffffe70} @tab 10
909 In this example, the caller's stack pointer would be at
912 The 80@var{x}86 convention for function return values is to place them
913 in the @samp{EAX} register. System calls that return a value can do
914 so by modifying the @samp{eax} member of @struct{intr_frame}.