Update docs.
[pintos-anon] / doc / userprog.texi
1 @node Project 2--User Programs, Project 3--Virtual Memory, Project 1--Threads, Top
2 @chapter Project 2: User Programs
3
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.
11
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}).
21
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.
28
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
33 this illusion.
34
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.
37
38 @menu
39 * Project 2 Code::              
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::    
46 * User Programs FAQ::           
47 * 80x86 Calling Convention::    
48 * System Calls::                
49 @end menu
50
51 @node Project 2 Code
52 @section Code
53
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:
58
59 @table @file
60 @item process.c
61 @itemx process.h
62 Loads ELF binaries and starts processes.
63
64 @item pagedir.c
65 @itemx pagedir.h
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.
70
71 @item syscall.c
72 @itemx syscall.h
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.
78
79 @item exception.c
80 @itemx exception.h
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.
89
90 @item gdt.c
91 @itemx gdt.c
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.
97
98 @item tss.c
99 @itemx tss.c
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
105 works.
106 @end table
107
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.
114
115 @node Using the File System
116 @section Using the File System
117
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.
129
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}.
137
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}.
146
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.
153
154 Here's a summary of how you would create and format a disk, copy the
155 @command{echo} program into the new disk, and then run @command{echo}.
156 It assumes that you've already built the tests in
157 @file{tests/userprog} and that the current directory is
158 @file{userprog/build}:
159
160 @example
161 pintos make-disk fs.dsk 2
162 pintos run -f
163 pintos put ../../tests/userprog/echo echo
164 pintos run -ex echo
165 @end example
166
167 You can delete a file from the Pintos file system using the @option{-r
168 @var{file}} kernel option, e.g.@: @code{pintos run -r @var{file}}.
169 Also, @option{-ls} lists the files in the file system and @option{-p
170 @var{file}} prints a file's contents to the display.
171
172 @node How User Programs Work
173 @section How User Programs Work
174
175 Pintos can run normal C programs.  In fact, it can run any program you
176 want, provided it's compiled into the proper file format, and uses
177 only the system calls you implement.  (For example, @func{malloc}
178 makes use of functionality that isn't provided by any of the syscalls
179 we require you to support.)  The only other limitation is that Pintos
180 can't run programs using floating point operations, since it doesn't
181 include the necessary kernel functionality to save and restore the
182 processor's floating-point unit when switching threads.  You can look
183 in @file{tests/userprog} directory for some examples.
184
185 Pintos loads ELF executables, where ELF is an executable format used
186 by Linux, Solaris, and many other Unix and Unix-like systems.
187 Therefore, you can use any compiler and linker that produce
188 80@var{x}86 ELF executables to produce programs for Pintos.  We
189 recommend using the tools we provide in the @file{tests/userprog}
190 directory.  By default, the @file{Makefile} in this directory will
191 compile the test programs we provide.  You can edit the
192 @file{Makefile} to compile your own test programs as well.
193
194 One thing you should realize immediately is that, until you copy a
195 test program to the emulated disk, Pintos will be unable to do very
196 much useful work.  You will also find that you won't be able to do
197 interesting things until you copy a variety of programs to the disk.
198 A useful technique is to create a clean reference disk and copy that
199 over whenever you trash your @file{fs.dsk} beyond a useful state,
200 which may happen occasionally while debugging.
201
202 @node Virtual Memory Layout
203 @section Virtual Memory Layout
204
205 Virtual memory in Pintos is divided into two regions: user virtual
206 memory and kernel virtual memory.  User virtual memory ranges from
207 virtual address 0 up to @code{PHYS_BASE}, which is defined in
208 @file{threads/mmu.h} and defaults to @t{0xc0000000} (3 GB).  Kernel
209 virtual memory occupies the rest of the virtual address space, from
210 @code{PHYS_BASE} up to 4 GB.
211
212 User virtual memory is per-process.  Conceptually, each process is
213 free to use the entire space of user virtual memory however it
214 chooses.  When the kernel switches from one process to another, it
215 also switches user virtual address spaces by switching the processor's
216 page directory base register (see @func{pagedir_activate in
217 @file{userprog/pagedir.c}}.  @struct{thread} contains a pointer to a
218 process's page directory.
219
220 Kernel virtual memory is global.  It is always mapped the same way,
221 regardless of what user process or kernel thread is running.  In
222 Pintos, kernel virtual memory is mapped one-to-one to physical
223 memory.  That is, virtual address @code{PHYS_ADDR} accesses physical
224 address 0, virtual address @code{PHYS_ADDR} + @t{0x1234} access
225 physical address @t{0x1234}, and so on up to the size of the machine's
226 physical memory.
227
228 User programs can only access user virtual memory.  An attempt to
229 access kernel virtual memory will cause a page fault, handled by
230 @func{page_fault} in @file{userprog/exception.c}, and the process
231 will be terminated.  Kernel threads can access both kernel virtual
232 memory and, if a user process is running, the user virtual memory of
233 the running process.  However, even in the kernel, an attempt to
234 access memory at a user virtual address that doesn't have a page
235 mapped into it will cause a page fault.
236
237 You must handle memory fragmentation gracefully, that is, a process
238 that needs @var{N} pages of memory must not require that all @var{N}
239 be contiguous.  In fact, it must not require that any of the pages be
240 contiguous.
241
242 @node Global Requirements
243 @section Global Requirements
244
245 For testing and grading purposes, we have some simple overall
246 requirements:
247
248 @itemize @bullet
249 @item
250 The kernel should print out the program's name and exit status whenever
251 a process terminates, whether termination is caused by the @code{exit}
252 system call or for another reason.
253
254 @itemize @minus
255 @item
256 The message must be formatted exactly as if it was printed with
257 @code{printf ("%s: exit(%d)\n", @dots{});} given appropriate arguments.
258
259 @item
260 The name printed should be the full name passed to
261 @func{process_execute}, except that it is acceptable to truncate it to
262 15 characters to allow for the limited space in @struct{thread}.  The
263 name printed need not include arguments.
264
265 @item
266 Do not print a message when a kernel thread that is not a process
267 terminates.
268
269 @item
270 Do not print messages about process termination for the @code{halt}
271 system call.
272
273 @item
274 No message need be printed when a process fails to load.
275 @end itemize
276
277 @item
278 Aside from this, the kernel should print out no other messages that
279 Pintos as provided doesn't already print.  You
280 may understand all those debug messages, but we won't, and it just
281 clutters our ability to see the stuff we care about.
282
283 @item
284 Additionally, while it may be useful to hard-code which process will
285 run at startup while debugging, before you submit your code you must
286 make sure that it takes the start-up process name and arguments from
287 the @samp{-ex} argument.  For example, running @code{pintos run -ex
288 "testprogram 1 2 3 4"} will spawn @samp{testprogram 1 2 3 4} as the
289 first process.
290 @end itemize
291
292 @node Problem 2-1 Argument Passing
293 @section Problem 2-1: Argument Passing
294
295 Currently, @func{process_execute} does not support passing arguments
296 to new processes.  UNIX and other operating systems do allow passing
297 command line arguments to a program, which accesses them via the argc,
298 argv arguments to main.  You must implement this functionality by
299 extending @func{process_execute} so that instead of simply taking a
300 program file name as its argument, it divides it into words at spaces.
301 The first word is the program name, the second word is the first
302 argument, and so on.  That is, @code{process_execute("grep foo bar")}
303 should run @command{grep} passing two arguments @code{foo} and
304 @file{bar}.  A few details:
305
306 @itemize
307 @item
308 Multiple spaces are considered the same as a single space, so that
309 @code{process_execute("grep foo bar")} would be equivalent to our
310 original example.
311
312 @item
313 You can impose a reasonable limit on the length of the command line
314 arguments.  For example, you could limit the arguments to those that
315 will fit in a single page (4 kB).
316
317 @item
318 You can parse the argument strings any way you like.  If you're lost,
319 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
320 implemented with thorough comments in @file{lib/string.c}.  You can
321 find more about it by looking at the man page (run @code{man strtok_r}
322 at the prompt).
323
324 @item
325 @xref{80x86 Calling Convention}, for information on exactly how you
326 need to set up the stack.
327 @end itemize
328
329 @strong{This functionality is extremely important.}  Almost all our
330 test cases rely on being able to pass arguments, so if you don't get
331 this right, a lot of things will not appear to work correctly with our
332 tests.  If the tests fail, so do you.  Fortunately, this part
333 shouldn't be too hard.
334
335 @node Problem 2-2 System Calls
336 @section Problem 2-2: System Calls
337
338 Implement the system call handler in @file{userprog/syscall.c} to
339 properly deal with all the system calls described below.  Currently,
340 it ``handles'' system calls by terminating the process.  You will need
341 to decipher system call arguments and take the appropriate action for
342 each.
343
344 You are required to support the following system calls, whose syscall
345 numbers are defined in @file{lib/syscall-nr.h} and whose C functions
346 called by user programs are prototyped in @file{lib/user/syscall.h}:
347
348 @table @code
349 @item SYS_halt
350 @itemx void halt (void)
351 Stops Pintos by calling @func{power_off} (declared in
352 @file{threads/init.h}).  Note that this should be seldom used, since
353 then you lose some information about possible deadlock situations,
354 etc.
355
356 @item SYS_exit
357 @itemx void exit (int @var{status})
358 Terminates the current user program, returning @var{status} to the
359 kernel.  If the process's parent @func{join}s it, this is the status
360 that will be returned.  Conventionally, a @var{status} of 0 indicates
361 a successful exit.  Other values may be used to indicate user-defined
362 conditions (usually errors).
363
364 @item SYS_exec
365 @itemx pid_t exec (const char *@var{cmd_line})
366 Runs the executable whose name is given in @var{cmd_line}, passing any
367 given arguments, and returns the new process's program id (pid).  If
368 there is an error loading this program, may return pid -1, which
369 otherwise should not be a valid id number.
370
371 @item SYS_join
372 @itemx int join (pid_t @var{pid})
373 Joins the process @var{pid}, using the join rules from the last
374 assignment, and returns the process's exit status.  If the process was
375 terminated by the kernel (i.e.@: killed due to an exception), the exit
376 status should be -1.  If the process was not a child of the calling
377 process, the return value is undefined (but kernel operation must not
378 be disrupted).
379
380 @item SYS_create
381 @itemx bool create (const char *@var{file}, unsigned @var{initial_size})
382 Create a new file called @var{file} initially @var{initial_size} bytes
383 in size.  Returns true if successful, false otherwise.
384
385 @item SYS_remove
386 @itemx bool remove (const char *@var{file})
387 Delete the file called @var{file}.  Returns true if successful, false
388 otherwise.
389
390 @item SYS_open
391 @itemx int open (const char *@var{file})
392 Open the file called @var{file}.  Returns a nonnegative integer handle
393 called a ``file descriptor'' (fd), or -1 if the file could not be
394 opened.  All open files associated with a process should be closed
395 when the process exits or is terminated.
396
397 File descriptors numbered 0 and 1 are reserved for the console: fd 0
398 is standard input (@code{stdin}), fd 1 is standard output
399 (@code{stdout}).  These special file descriptors are valid as system
400 call arguments only as explicitly described below.
401
402 @item SYS_filesize
403 @itemx int filesize (int @var{fd})
404 Returns the size, in bytes, of the file open as @var{fd}.
405
406 @item SYS_read
407 @itemx int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
408 Read @var{size} bytes from the file open as @var{fd} into
409 @var{buffer}.  Returns the number of bytes actually read (0 at end of
410 file), or -1 if the file could not be read (due to a condition other
411 than end of file).  Fd 0 reads from the keyboard using
412 @func{kbd_getc}.
413
414 @item SYS_write
415 @itemx int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
416 Write @var{size} bytes from @var{buffer} to the open file @var{fd}.
417 Returns the number of bytes actually written, or -1 if the file could
418 not be written.   Fd 1 writes to the console.
419
420 @item SYS_seek
421 @itemx void seek (int @var{fd}, unsigned @var{position})
422 Changes the next byte to be read or written in open file @var{fd} to
423 @var{position}, expressed in bytes from the beginning of the file.
424 (Thus, a @var{position} of 0 is the file's start.)
425
426 A seek past the current end of a file is not an error.  A later read
427 obtains 0 bytes, indicating end of file.  A later write extends the
428 file, filling any unwritten gap with zeros.  (However, in Pintos files
429 have a fixed length until project 4 is complete, so writes past end of
430 file will return an error.)  These semantics are implemented in the
431 file system and do not require any special effort in system call
432 implementation.
433
434 @item SYS_tell
435 @itemx unsigned tell (int @var{fd})
436 Returns the position of the next byte to be read or written in open
437 file @var{fd}, expressed in bytes from the beginning of the file.
438
439 @item SYS_close
440 @itemx void close (int @var{fd})
441 Close file descriptor @var{fd}.
442 @end table
443
444 The file defines other syscalls.  Ignore them for now.  You will
445 implement some of them in project 3 and the rest in project 4, so be
446 sure to design your system with extensibility in mind.
447
448 To implement syscalls, you will need to provide a way of copying data
449 from the user's virtual address space into the kernel and vice versa.
450 This can be a bit tricky: what if the user provides an invalid
451 pointer, a pointer into kernel memory, or points to a block that is
452 partially in one of those regions?  You should handle these cases by
453 terminating the user process.  You will need this code before you can
454 even obtain the system call number, because the system call number is
455 on the user's stack in the user's virtual address space.  We recommend
456 writing and testing this code before implementing any other system
457 call functionality.
458
459 You must make sure that system calls are properly synchronized so that
460 any number of user processes can make them at once.  In particular, it
461 is not safe to call into the filesystem code provided in the
462 @file{filesys} directory from multiple threads at once.  For now, we
463 recommend adding a single lock that controls access to the filesystem
464 code.  You should acquire this lock before calling any functions in
465 the @file{filesys} directory, and release it afterward.  Don't forget
466 that @func{process_execute} also accesses files.  @strong{For now, we
467 recommend against modifying code in the @file{filesys} directory.}
468
469 We have provided you a user-level function for each system call in
470 @file{lib/user/syscall.c}.  These provide a way for user processes to
471 invoke each system call from a C program.  Each of them calls an
472 assembly language routine in @file{lib/user/syscall-stub.S}, which in
473 turn invokes the system call interrupt and returns.
474
475 When you're done with this part, and forevermore, Pintos should be
476 bulletproof.  Nothing that a user program can do should ever cause the
477 OS to crash, halt, assert fail, or otherwise stop running.  The sole
478 exception is a call to the @code{halt} system call.
479
480 If a system call is passed an invalid argument, acceptable options
481 include returning an error value (for those calls that return a
482 value), returning an undefined value, or terminating the process.
483
484 @xref{System Calls}, for more information on how syscalls work.
485
486 @node User Programs FAQ
487 @section FAQ
488
489 @enumerate 1
490 @item
491 @b{Do we need a working project 1 to implement project 2?}
492
493 You may find the code for @func{thread_join} to be useful in
494 implementing the join syscall, but besides that, you can use
495 the original code provided for project 1.
496
497 @item
498 @b{@samp{pintos put} always panics.}
499
500 Here are the most common causes:
501
502 @itemize @bullet
503 @item
504 The disk hasn't yet been formatted (with @samp{pintos run -f}).
505
506 @item
507 The filename specified is too long.  The file system limits file names
508 to 14 characters.  If you're using a command like @samp{pintos put
509 ../../tests/userprog/echo}, that overflows the limit.  Use
510 @samp{pintos put ../../tests/userprog/echo echo} to put the file under
511 the name @file{echo} instead.
512
513 @item
514 The file is too big.  The file system has a 63 kB limit.
515 @end itemize
516
517 @item
518 @b{All my user programs die with page faults.}
519
520 This will generally happen if you haven't implemented problem 2-1
521 yet.  The reason is that the basic C library for user programs tries
522 to read @var{argc} and @var{argv} off the stack.  Because the stack
523 isn't properly set up yet, this causes a page fault.
524
525 @item
526 @b{I implemented 2-1 and now all my user programs die with
527 @samp{system call!}.}
528
529 Every reasonable program tries to make at least one system call
530 (@func{exit}) and most programs make more than that.  Notably,
531 @func{printf} invokes the @code{write} system call.  The default
532 system call handler just prints @samp{system call!} and terminates the
533 program.  You'll have to implement 2-2 before you see anything more
534 interesting.  Until then, you can use @func{hex_dump} to convince
535 yourself that 2-1 is implemented correctly (@pxref{Argument Passing to
536 main}).
537
538 @item
539 @b{Is there a way I can disassemble user programs?}
540
541 The @command{i386-elf-objdump} utility can disassemble entire user
542 programs or object files.  Invoke it as @code{i386-elf-objdump -d
543 @var{file}}.  You can also use @code{i386-elf-gdb}'s
544 @command{disassemble} command to disassemble individual functions in
545 object files compiled with debug information.
546
547 @item
548 @b{Why can't I use many C include files in my Pintos programs?}
549
550 The C library we provide is very limited.  It does not include many of
551 the features that are expected of a real operating system's C library.
552 The C library must be built specifically for the operating system (and
553 architecture), since it must make system calls for I/O and memory
554 allocation.  (Not all functions do, of course, but usually the library
555 is compiled as a unit.)
556
557 @item
558 @b{Can I use lib@var{foo} in my Pintos programs?}
559
560 The chances are good that lib@var{foo} uses parts of the C library
561 that Pintos doesn't implement.  It will probably take at least some
562 porting effort to make it work under Pintos.  Notably, the Pintos
563 userland C library does not have a @func{malloc} implementation.
564
565 @item
566 @b{How do I compile new user programs?}
567
568 You need to modify @file{tests/Makefile}.
569
570 @item
571 @b{What's the difference between @code{tid_t} and @code{pid_t}?}
572
573 A @code{tid_t} identifies a kernel thread, which may have a user
574 process running in it (if created with @func{process_execute}) or not
575 (if created with @func{thread_create}).  It is a data type used only
576 in the kernel.
577
578 A @code{pid_t} identifies a user process.  It is used by user
579 processes and the kernel in the @code{exec} and @code{join} system
580 calls.
581
582 You can choose whatever suitable types you like for @code{tid_t} and
583 @code{pid_t}.  By default, they're both @code{int}.  You can make them
584 a one-to-one mapping, so that the same values in both identify the
585 same process, or you can use a more complex mapping.  It's up to you.
586
587 @item
588 @b{I can't seem to figure out how to read from and write to user
589 memory. What should I do?}
590
591 The kernel must treat user memory delicately.  As part of a system
592 call, the user can pass to the kernel a null pointer, a pointer to
593 unmapped virtual memory, or a pointer to kernel virtual address space
594 (above @code{PHYS_BASE}).  All of these types of invalid pointers must
595 be rejected without harm to the kernel or other running processes.  At
596 your option, the kernel may handle invalid pointers by terminating the
597 process or returning from the system call with an error.
598
599 There are at least two reasonable ways to do this correctly.  The
600 first method is to ``verify then access'':@footnote{These terms are
601 made up for this document.  They are not standard terminology.} verify
602 the validity of a user-provided pointer, then dereference it.  If you
603 choose this route, you'll want to look at the functions in
604 @file{userprog/pagedir.c} and in @file{threads/mmu.h}.  This is the
605 simplest way to handle user memory access.
606
607 The second method is to ``assume and react'': directly dereference
608 user pointers, after checking that they point below @code{PHYS_BASE}.
609 Invalid user pointers will then cause a ``page fault'' that you can
610 handle by modifying the code for @func{page_fault} in
611 @file{userprog/exception.cc}.  This technique is normally faster
612 because it takes advantage of the processor's MMU, so it tends to be
613 used in real kernels (including Linux).
614
615 In either case, you need to make sure not to ``leak'' resources.  For
616 example, suppose that your system call has acquired a lock or
617 allocated a page of memory.  If you encounter an invalid user pointer
618 afterward, you must still be sure to release the lock or free the page
619 of memory.  If you choose to ``verify then access,'' then this should
620 be straightforward, but for ``assume and react'' it's more difficult,
621 because there's no way to return an error code from a memory access.
622 Therefore, for those who want to try the latter technique, we'll
623 provide a little bit of helpful code:
624
625 @verbatim
626 /* Tries to copy a byte from user address USRC to kernel address DST.
627    Returns true if successful, false if USRC is invalid. */
628 static inline bool get_user (uint8_t *dst, const uint8_t *usrc) {
629   int eax;
630   asm ("movl $1f, %%eax; movb %2, %%al; movb %%al, %0; 1:"
631        : "=m" (*dst), "=&a" (eax) : "m" (*usrc));
632   return eax != 0;
633 }
634
635 /* Tries write BYTE to user address UDST.
636    Returns true if successful, false if UDST is invalid. */
637 static inline bool put_user (uint8_t *udst, uint8_t byte) {
638   int eax;
639   asm ("movl $1f, %%eax; movb %b2, %0; 1:"
640        : "=m" (*udst), "=&a" (eax) : "r" (byte));
641   return eax != 0;
642 }
643 @end verbatim
644
645 Each of these functions assumes that the user address has already been
646 verified to be below @code{PHYS_BASE}.  They also assume that you've
647 modified @func{page_fault} so that a page fault in the kernel causes
648 @code{eax} to be set to 0 and its former value copied into @code{eip}.
649
650 @item
651 @b{I'm also confused about reading from and writing to the stack. Can
652 you help?}
653
654 @itemize @bullet
655 @item
656 Only non-@samp{char} values will have issues when writing them to
657 memory.  If a digit is in a string, it is considered a character.
658 However, the value of @code{argc} would be a non-char.
659
660 @item
661 You will need to write characters and non-characters into main memory.
662
663 @item
664 When you add items to the stack, you will be decrementing the stack
665 pointer.  You'll need to decrement the stack pointer before writing to
666 the location.
667
668 @item
669 Each character is 1 byte.
670 @end itemize
671
672 @item
673 @b{Why doesn't keyboard input work with @samp{pintos -v}?}
674
675 Serial input isn't implemented.  Don't use @samp{pintos -v} if you
676 want to use the shell or otherwise provide keyboard input.
677 @end enumerate
678
679 @menu
680 * Problem 2-1 Argument Passing FAQ::  
681 * Problem 2-2 System Calls FAQ::  
682 @end menu
683
684 @node Problem 2-1 Argument Passing FAQ
685 @subsection Problem 2-1: Argument Passing FAQ
686
687 @enumerate 1
688 @item
689 @b{Why is the top of the stack at @t{0xc0000000}?  Isn't that off the
690 top of user virtual memory?  Shouldn't it be @t{0xbfffffff}?}
691
692 When the processor pushes data on the stack, it decrements the stack
693 pointer first.  Thus, the first (4-byte) value pushed on the stack
694 will be at address @t{0xbffffffc}.
695
696 Also, the stack should always be aligned to a 4-byte boundary, but
697 @t{0xbfffffff} isn't.
698
699 @item
700 @b{Is @code{PHYS_BASE} fixed?}
701
702 No.  You should be able to support @code{PHYS_BASE} values that are
703 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xc0000000},
704 simply via recompilation.
705 @end enumerate
706
707 @node Problem 2-2 System Calls FAQ
708 @subsection Problem 2-2: System Calls FAQ
709
710 @enumerate 1
711 @item
712 @b{Can I just cast a pointer to a @struct{file} object to get a
713 unique file descriptor?  Can I just cast a @code{struct thread *} to a
714 @code{pid_t}?  It's so much simpler that way!}
715
716 This is a design decision you will have to make for yourself.
717 However, note that most operating systems do distinguish between file
718 descriptors (or pids) and the addresses of their kernel data
719 structures.  You might want to give some thought as to why they do so
720 before committing yourself.
721
722 @item
723 @b{Can I set a maximum number of open files per process?}
724
725 From a design standpoint, it would be better not to set an arbitrary
726 maximum.  That said, if your design calls for it, you may impose a
727 limit of 128 open files per process (as the Solaris machines here do).
728
729 @item
730 @anchor{Removing an Open File}
731 @b{What happens when two (or more) processes have a file open and one of
732 them removes it?}
733
734 You should copy the standard Unix semantics for files.  That is, when
735 a file is removed an process which has a file descriptor for that file
736 may continue to do operations on that descriptor.  This means that
737 they can read and write from the file.  The file will not have a name,
738 and no other processes will be able to open it, but it will continue
739 to exist until all file descriptors referring to the file are closed
740 or the machine shuts down.
741
742 @item
743 @b{I've discovered that some of my user programs need more than one 4
744 kB page of stack space.  What should I do?}
745
746 You may modify the stack setup code to allocate more than one page of
747 stack space for each process.
748 @end enumerate
749
750 @node 80x86 Calling Convention
751 @section 80@var{x}86 Calling Convention
752
753 What follows is a quick and dirty discussion of the 80@var{x}86
754 calling convention.  Some of the basics should be familiar from CS
755 107, and if you've already taken CS 143 or EE 182, then you should
756 have seen even more of it.  I've omitted some of the complexity, since
757 this isn't a class in how function calls work, so don't expect this to
758 be exactly correct in full, gory detail.  If you do want all the
759 details, you can refer to @bibref{SysV-i386}.
760
761 Whenever a function call happens, you need to put the arguments on the
762 call stack for that function, before the code for that function
763 executes, so that the callee has access to those values.  The caller
764 has to be responsible for this (be sure you understand why).
765 Therefore, when you compile a program, the assembly code emitted will
766 have in it, before every function call, a bunch of instructions that
767 prepares for the call in whatever manner is conventional for the
768 machine you're working on.  This includes saving registers as needed,
769 putting stuff on the stack, saving the location to return to somewhere
770 (so that when the callee finishes, it knows where the caller code is),
771 and some other bookkeeping stuff.  Then you do the jump to the
772 callee's code, and it goes along, assuming that the stack and
773 registers are prepared in the appropriate manner.  When the callee is
774 done, it looks at the return location as saved earlier, and jumps back
775 to that location.  The caller may then have to do some cleanup:
776 clearing arguments and the return value off the stack, restoring
777 registers that were saved before the call, and so on.
778
779 If you think about it, some of these things should remind you of
780 context switching.
781
782 As an aside, in general, function calls are not cheap.  You have to do
783 a bunch of memory writes to prepare the stack, you need to save and
784 restore registers before and after a function call, you need to write
785 the stack pointer, you have a couple of jumps which probably wrecks
786 some of your caches.  This is why inlining code can be much faster.
787
788 @menu
789 * Argument Passing to main::    
790 @end menu
791
792 @node Argument Passing to main
793 @subsection Argument Passing to @code{main()}
794
795 In @func{main}'s case, there is no caller to prepare the stack
796 before it runs.  Therefore, the kernel needs to do it.  Fortunately,
797 since there's no caller, there are no registers to save, no return
798 address to deal with, etc.  The only difficult detail to take care of,
799 after loading the code, is putting the arguments to @func{main} on
800 the stack.
801
802 (The above is a small lie: most compilers will emit code where main
803 isn't strictly speaking the first function.  This isn't an important
804 detail.  If you want to look into it more, try disassembling a program
805 and looking around a bit.  However, you can just act as if
806 @func{main} is the very first function called.)
807
808 Pintos is written for the 80@var{x}86 architecture.  Therefore, we
809 need to adhere to the 80@var{x}86 calling convention.  Basically, you
810 put all the arguments on the stack and move the stack pointer
811 appropriately.  You also need to insert space for the function's
812 ``return address'': even though the initial function doesn't really
813 have a caller, its stack frame must have the same layout as any other
814 function's.  The program will assume that the stack has been laid out
815 this way when it begins running.
816
817 So, what are the arguments to @func{main}? Just two: an @samp{int}
818 (@code{argc}) and a @samp{char **} (@code{argv}).  @code{argv} is an
819 array of strings, and @code{argc} is the number of strings in that
820 array.  However, the hard part isn't these two things.  The hard part
821 is getting all the individual strings in the right place.  As we go
822 through the procedure, let us consider the following example command:
823 @samp{/bin/ls -l foo bar}.
824
825 The first thing to do is to break the command line into individual
826 strings: @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}.  These
827 constitute the arguments of the command, including the program name
828 itself (which belongs in @code{argv[0]}).
829
830 These individual, null-terminated strings should be placed on the user
831 stack.  They may be placed in any order, as you'll see shortly,
832 without affecting how main works, but for simplicity let's assume they
833 are in reverse order (keeping in mind that the stack grows downward on
834 an 80@var{x}86 machine).  As we copy the strings onto the stack, we
835 record their (virtual) stack addresses.  These addresses will become
836 important when we write the argument vector (two paragraphs down).
837
838 After we push all of the strings onto the stack, we adjust the stack
839 pointer so that it is word-aligned: that is, we move it down to the
840 next 4-byte boundary.  This is required because we will next be
841 placing several words of data on the stack, and they must be aligned
842 to be read correctly.  In our example, as you'll see below,
843 the strings start at address @t{0xffed}.  One word below that would be
844 at @t{0xffe9}, so we could in theory put the next word on the stack
845 there.  However, since the stack pointer should always be
846 word-aligned, we instead leave the stack pointer at @t{0xffe8}.
847
848 Once we align the stack pointer, we then push the elements of the
849 argument vector, that is, a null pointer, then the addresses of the
850 strings @samp{/bin/ls}, @samp{-l}, @samp{foo}, and @samp{bar}) onto
851 the stack.  This must be done in reverse order, such that
852 @code{argv[0]} is at the lowest virtual address, again because the
853 stack is growing downward.  (The null pointer pushed first is because
854 @code{argv[argc]} must be a null pointer.)  This is because we are now
855 writing the actual array of strings; if we write them in the wrong
856 order, then the strings will be in the wrong order in the array.  This
857 is also why, strictly speaking, it doesn't matter what order the
858 strings themselves are placed on the stack: as long as the pointers
859 are in the right order, the strings themselves can really be anywhere.
860 After we finish, we note the stack address of the first element of the
861 argument vector, which is @code{argv} itself.
862
863 Then we push @code{argv} (that is, the address of the first element of
864 the @code{argv} array) onto the stack, along with the length of the
865 argument vector (@code{argc}, 4 in this example).  This must also be
866 done in this order, since @code{argc} is the first argument to
867 @func{main} and therefore is on first (smaller address) on the
868 stack.  Finally, we push a fake ``return address'' and leave the stack
869 pointer to point to its location.
870
871 All this may sound very confusing, so here's a picture which will
872 hopefully clarify what's going on. This represents the state of the
873 stack and the relevant registers right before the beginning of the
874 user program (assuming for this example that the stack bottom is
875 @t{0xc0000000}):
876
877 @html
878 <CENTER>
879 @end html
880 @multitable {@t{0xbfffffff}} {``return address''} {@t{/bin/ls\0}}
881 @item Address @tab Name @tab Data
882 @item @t{0xbffffffc} @tab @code{*argv[3]} @tab @samp{bar\0}
883 @item @t{0xbffffff8} @tab @code{*argv[2]} @tab @samp{foo\0}
884 @item @t{0xbffffff5} @tab @code{*argv[1]} @tab @samp{-l\0}
885 @item @t{0xbfffffed} @tab @code{*argv[0]} @tab @samp{/bin/ls\0}
886 @item @t{0xbfffffec} @tab word-align @tab @samp{\0}
887 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0}
888 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc}
889 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8}
890 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5}
891 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed}
892 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8}
893 @item @t{0xbfffffd0} @tab @code{argc} @tab 4
894 @item @t{0xbfffffcc} @tab ``return address'' @tab 0
895 @end multitable
896 @html
897 </CENTER>
898 @end html
899
900 In this example, the stack pointer would be initialized to
901 @t{0xbfffffcc}.
902
903 As shown above, your code should start the stack at the very top of
904 the user virtual address space, in the page just below virtual address
905 @code{PHYS_BASE} (defined in @file{threads/mmu.h}).
906
907 You may find the non-standard @func{hex_dump} function, declared in
908 @file{<stdio.h>}, useful for debugging your argument passing code.
909 Here's what it would show in the above example, given that
910 @code{PHYS_BASE} is @t{0xc0000000}:
911
912 @verbatim
913 bfffffc0                                      00 00 00 00 |            ....|
914 bfffffd0  04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
915 bfffffe0  f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
916 bffffff0  6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
917 @end verbatim
918
919 @node System Calls
920 @section System Calls
921
922 We have already been dealing with one way that the operating system
923 can regain control from a user program: interrupts from timers and I/O
924 devices.  These are ``external'' interrupts, because they are caused
925 by entities outside the CPU.
926
927 The operating system is also called to deal with software exceptions,
928 which are events generated in response to the code.  These can be
929 errors such as a page fault or division by zero.  However, exceptions
930 are also the means by which a user program can request services
931 (``system calls'') from the operating system.
932
933 In the 80@var{x}86 architecture, the @samp{int} instruction is the
934 most commonly used means for invoking system calls.  This instruction
935 is handled in the same way as other software exceptions.  In Pintos,
936 user programs invoke @samp{int $0x30} to make a system call.  The
937 system call number and any additional arguments are expected to be
938 pushed on the stack in the normal fashion before invoking the
939 interrupt.
940
941 The normal calling convention pushes function arguments on the stack
942 from right to left and the stack grows downward.  Thus, when the
943 system call handler @func{syscall_handler} gets control, the system
944 call number is in the 32-bit word at the caller's stack pointer, the
945 first argument is in the 32-bit word at the next higher address, and
946 so on.  The caller's stack pointer is accessible to
947 @func{syscall_handler} as the @samp{esp} member of the @code{struct
948 intr_frame} passed to it.
949
950 Here's an example stack frame for calling a system call numbered 10
951 with three arguments passed as 1, 2, and 3.  The stack addresses are
952 arbitrary:
953
954 @html
955 <CENTER>
956 @end html
957 @multitable {@t{0xbffffe7c}} {Value}
958 @item Address @tab Value
959 @item @t{0xbffffe7c} @tab 3
960 @item @t{0xbffffe78} @tab 2
961 @item @t{0xbffffe74} @tab 1
962 @item @t{0xbffffe70} @tab 10
963 @end multitable
964 @html
965 </CENTER>
966 @end html
967
968 In this example, the caller's stack pointer would be at
969 @t{0xbffffe70}.
970
971 The 80@var{x}86 convention for function return values is to place them
972 in the @samp{EAX} register.  System calls that return a value can do
973 so by modifying the @samp{eax} member of @struct{intr_frame}.
974
975 You should try to avoid writing large amounts of repetitive code for
976 implementing system calls.  Each system call argument, whether an
977 integer or a pointer, takes up 4 bytes on the stack.  You should be able
978 to take advantage of this to avoid writing much near-identical code for
979 retrieving each system call's arguments from the stack.