9d80e375669819c5a43da14ae4009c85f7d344f8
[pintos-anon] / userprog.texi
1 @node Project 2--User Programs
2 @chapter Project 2: User Programs
3
4 Now that you've worked with Pintos and are becoming familiar with its
5 infrastructure and thread package, it's time to start working on the
6 parts of the system that allow running user programs.
7 The base code already supports loading and
8 running user programs, but no I/O or interactivity
9 is possible.  In this project, you will enable programs to interact with
10 the OS via system calls.
11
12 You will be working out of the @file{userprog} directory for this
13 assignment, but you will also be interacting with almost every
14 other part of Pintos.  We will describe the
15 relevant parts below.
16
17 You can build project 2 on top of your project 1 submission or you can
18 start fresh.  No code from project 1 is required for this
19 assignment.  The ``alarm clock'' functionality may be useful in
20 projects 3 and 4, but it is not strictly required.
21
22 You might find it useful to go back and reread how to run the tests
23 (@pxref{Testing}).
24
25 @menu
26 * Project 2 Background::        
27 * Project 2 Suggested Order of Implementation::  
28 * Project 2 Requirements::      
29 * Project 2 FAQ::               
30 * 80x86 Calling Convention::    
31 @end menu
32
33 @node Project 2 Background
34 @section Background
35
36 Up to now, all of the code you have run under Pintos has been part
37 of the operating system kernel.  This means, for example, that all the
38 test code from the last assignment ran as part of the kernel, with
39 full access to privileged parts of the system.  Once we start running
40 user programs on top of the operating system, this is no longer true.
41 This project deals with the consequences.
42
43 We allow more than one process to run at a time.  Each process has one
44 thread (multithreaded processes are not supported).  User programs are
45 written under the illusion that they have the entire machine.  This
46 means that when you load and run multiple processes at a time, you must
47 manage memory, scheduling, and other state correctly to maintain this
48 illusion.
49
50 In the previous project, we compiled our test code directly into your
51 kernel, so we had to require certain specific function interfaces within
52 the kernel.  From now on, we will test your operating system by running
53 user programs.  This gives you much greater freedom.  You must make sure
54 that the user program interface meets the specifications described here,
55 but given that constraint you are free to restructure or rewrite kernel
56 code however you wish.
57
58 @menu
59 * Project 2 Source Files::      
60 * Using the File System::       
61 * How User Programs Work::      
62 * Virtual Memory Layout::       
63 * Accessing User Memory::       
64 @end menu
65
66 @node Project 2 Source Files
67 @subsection Source Files
68
69 The easiest way to get an overview of the programming you will be
70 doing is to simply go over each part you'll be working with.  In
71 @file{userprog}, you'll find a small number of files, but here is
72 where the bulk of your work will be:
73
74 @table @file
75 @item process.c
76 @itemx process.h
77 Loads ELF binaries and starts processes.
78
79 @item pagedir.c
80 @itemx pagedir.h
81 A simple manager for 80@var{x}86 hardware page tables.
82 Although you probably won't want to modify this code for this project,
83 you may want to call some of its functions.
84 @xref{Page Tables}, for more information.
85
86 @item syscall.c
87 @itemx syscall.h
88 Whenever a user process wants to access some kernel functionality, it
89 invokes a system call.  This is a skeleton system call
90 handler.  Currently, it just prints a message and terminates the user
91 process.  In part 2 of this project you will add code to do everything
92 else needed by system calls.
93
94 @item exception.c
95 @itemx exception.h
96 When a user process performs a privileged or prohibited operation, it
97 traps into the kernel as an ``exception'' or ``fault.''@footnote{We
98 will treat these terms as synonyms.  There is no standard
99 distinction between them, although Intel processor manuals make 
100 a minor distinction between them on 80@var{x}86.}  These files handle
101 exceptions.  Currently all exceptions simply print a message and
102 terminate the process.  Some, but not all, solutions to project 2
103 require modifying @func{page_fault} in this file.
104
105 @item gdt.c
106 @itemx gdt.h
107 The 80@var{x}86 is a segmented architecture.  The Global Descriptor
108 Table (GDT) is a table that describes the segments in use.  These
109 files set up the GDT.  You should not need to modify these
110 files for any of the projects.  You can read the code if
111 you're interested in how the GDT works.
112
113 @item tss.c
114 @itemx tss.h
115 The Task-State Segment (TSS) is used for 80@var{x}86 architectural
116 task switching.  Pintos uses the TSS only for switching stacks when a
117 user process enters an interrupt handler, as does Linux.  You
118 should not need to modify these files for any of the projects.
119 You can read the code if you're interested in how the TSS
120 works.
121 @end table
122
123 @node Using the File System
124 @subsection Using the File System
125
126 You will need to interface to the file system code for this project,
127 because
128 user programs are loaded from the file system and many of the
129 system calls you must implement deal with the file system.  However,
130 the focus of this project is not the file system, so we have
131 provided a simple but complete file system in the @file{filesys}
132 directory.  You
133 will want to look over the @file{filesys.h} and @file{file.h}
134 interfaces to understand how to use the file system, and especially
135 its many limitations.
136
137 There is no need to modify the file system code for this project, and so
138 we recommend that you do not.  Working on the file system is likely to
139 distract you from this project's focus.
140
141 Proper use of the file system routines now
142 will make life much easier for project 4, when you improve the file
143 system implementation.  Until then, you will have to tolerate the
144 following limitations:
145
146 @itemize @bullet
147 @item
148 No internal synchronization.  Concurrent accesses will interfere with one
149 another.  You should use synchronization to ensure that only one process at a
150 time is executing file system code.
151
152 @item
153 File size is fixed at creation time.  The root directory is
154 represented as a file, so the number of files that may be created is also
155 limited.
156
157 @item
158 File data is allocated as a single extent, that is, data in a single
159 file must occupy a contiguous range of sectors on disk.  External
160 fragmentation can therefore become a serious problem as a file system is
161 used over time.
162
163 @item
164 No subdirectories.
165
166 @item
167 File names are limited to 14 characters.
168
169 @item
170 A system crash mid-operation may corrupt the disk in a way
171 that cannot be repaired automatically.  There is no file system repair
172 tool anyway.
173 @end itemize
174
175 One important feature is included:
176
177 @itemize @bullet
178 @item
179 Unix-like semantics for @func{filesys_remove} are implemented.
180 That is, if a file is open when it is removed, its blocks
181 are not deallocated and it may still be accessed by any
182 threads that have it open, until the last one closes it.  @xref{Removing
183 an Open File}, for more information.
184 @end itemize
185
186 You need to be able to create simulated disks.  The
187 @command{pintos-mkdisk} program provides this functionality.  From the
188 @file{userprog/build} directory, execute @code{pintos-mkdisk fs.dsk@tie{}2}.
189 This command creates a 2 MB simulated disk named @file{fs.dsk}.  Then
190 format the disk by passing @option{-f -q} on the kernel's command
191 line: @code{pintos -f -q}.  The @option{-f} option causes the disk to be
192 formatted, and @option{-q} causes Pintos to exit as soon as the format
193 is done.
194
195 You'll need a way to copy files in and out of the simulated file system.
196 The @code{pintos} @option{-p} (``put'') and @option{-g} (``get'')
197 options do this.  To copy @file{@var{file}} into the
198 Pintos file system, use the command @file{pintos -p @var{file} -- -q}.
199 (The @samp{--} is needed because @option{-p} is for the @command{pintos}
200 script, not for the simulated kernel.)  To copy it to the Pintos file
201 system under the name @file{@var{newname}}, add @option{-a
202 @var{newname}}: @file{pintos -p @var{file} -a @var{newname} -- -q}.  The
203 commands for copying files out of a VM are similar, but substitute
204 @option{-g} for @option{-p}.
205
206 Incidentally, these commands work by passing special commands
207 @command{extract} and @command{append} on the kernel's command line and copying
208 to and from a special simulated ``scratch'' disk.  If you're very
209 curious, you can look at the @command{pintos} script as well as
210 @file{filesys/fsutil.c} to learn the implementation details.
211
212 Here's a summary of how to create and format a disk, copy the
213 @command{echo} program into the new disk, and then run @command{echo},
214 passing argument @code{x}.  (Argument passing won't work until
215 you implemented it.)  It assumes
216 that you've already built the
217 examples in @file{examples} and that the current directory is
218 @file{userprog/build}:
219
220 @example
221 pintos-mkdisk fs.dsk 2
222 pintos -f -q
223 pintos -p ../../examples/echo -a echo -- -q
224 pintos -q run 'echo x'
225 @end example
226
227 The three final steps can actually be combined into a single command:
228
229 @example
230 pintos-mkdisk fs.dsk 2
231 pintos -p ../../examples/echo -a echo -- -f -q run 'echo x'
232 @end example
233
234 If you don't want to keep the file system disk around for later use or
235 inspection, you can even combine all four steps into a single command.
236 The @code{--fs-disk=@var{n}} option creates a temporary disk
237 approximately @var{n} megabytes in size just for the duration of the
238 @command{pintos} run.  The Pintos automatic test suite makes extensive
239 use of this syntax:
240
241 @example
242 pintos --fs-disk=2 -p ../../examples/echo -a echo -- -f -q run 'echo x'
243 @end example
244
245 You can delete a file from the Pintos file system using the @code{rm
246 @var{file}} kernel action, e.g.@: @code{pintos -q rm @var{file}}.  Also,
247 @command{ls} lists the files in the file system and @code{cat
248 @var{file}} prints a file's contents to the display.
249
250 @node How User Programs Work
251 @subsection How User Programs Work
252
253 Pintos can run normal C programs, as long as they fit into memory and use
254 only the system calls you implement.  Notably, @func{malloc} cannot be
255 implemented because none of the system calls required for this project
256 allow for memory allocation.  Pintos also can't run programs that use
257 floating point operations, since the kernel doesn't save and restore the
258 processor's floating-point unit when switching threads.
259
260 The @file{src/examples} directory contains a few sample user
261 programs.  The @file{Makefile} in this directory
262 compiles the provided examples, and you can edit it
263 compile your own programs as well.  Some of the example programs will
264 only work once projects 3 or 4 have been implemented.
265
266 Pintos can load @dfn{ELF} executables with the loader provided for you
267 in @file{userprog/process.c}.  ELF is a file format used by Linux,
268 Solaris, and many other operating systems for object files,
269 shared libraries, and executables.  You can actually use any compiler
270 and linker that output 80@var{x}86 ELF executables to produce programs
271 for Pintos.  (We've provided compilers and linkers that should do just
272 fine.)
273
274 You should realize immediately that, until you copy a
275 test program to the simulated disk, Pintos will be unable to do
276 useful work.  You won't be able to do
277 interesting things until you copy a variety of programs to the disk.
278 You might want to create a clean reference disk and copy that
279 over whenever you trash your @file{fs.dsk} beyond a useful state,
280 which may happen occasionally while debugging.
281
282 @node Virtual Memory Layout
283 @subsection Virtual Memory Layout
284
285 Virtual memory in Pintos is divided into two regions: user virtual
286 memory and kernel virtual memory.  User virtual memory ranges from
287 virtual address 0 up to @code{PHYS_BASE}, which is defined in
288 @file{threads/vaddr.h} and defaults to @t{0xc0000000} (3 GB).  Kernel
289 virtual memory occupies the rest of the virtual address space, from
290 @code{PHYS_BASE} up to 4 GB.
291
292 User virtual memory is per-process.
293 When the kernel switches from one process to another, it
294 also switches user virtual address spaces by changing the processor's
295 page directory base register (see @func{pagedir_activate} in
296 @file{userprog/pagedir.c}).  @struct{thread} contains a pointer to a
297 process's page table.
298
299 Kernel virtual memory is global.  It is always mapped the same way,
300 regardless of what user process or kernel thread is running.  In
301 Pintos, kernel virtual memory is mapped one-to-one to physical
302 memory, starting at @code{PHYS_BASE}.  That is, virtual address
303 @code{PHYS_BASE} accesses physical
304 address 0, virtual address @code{PHYS_BASE} + @t{0x1234} accesses
305 physical address @t{0x1234}, and so on up to the size of the machine's
306 physical memory.
307
308 A user program can only access its own user virtual memory.  An attempt to
309 access kernel virtual memory causes a page fault, handled by
310 @func{page_fault} in @file{userprog/exception.c}, and the process
311 will be terminated.  Kernel threads can access both kernel virtual
312 memory and, if a user process is running, the user virtual memory of
313 the running process.  However, even in the kernel, an attempt to
314 access memory at an unmapped user virtual address
315 will cause a page fault.
316
317 @menu
318 * Typical Memory Layout::       
319 @end menu
320
321 @node Typical Memory Layout
322 @subsubsection Typical Memory Layout
323
324 Conceptually, each process is
325 free to lay out its own user virtual memory however it
326 chooses.  In practice, user virtual memory is laid out like this:
327
328 @html
329 <CENTER>
330 @end html
331 @example
332 @group
333    PHYS_BASE +----------------------------------+
334              |            user stack            |
335              |                 |                |
336              |                 |                |
337              |                 V                |
338              |          grows downward          |
339              |                                  |
340              |                                  |
341              |                                  |
342              |                                  |
343              |           grows upward           |
344              |                 ^                |
345              |                 |                |
346              |                 |                |
347              +----------------------------------+
348              | uninitialized data segment (BSS) |
349              +----------------------------------+
350              |     initialized data segment     |
351              +----------------------------------+
352              |           code segment           |
353   0x08048000 +----------------------------------+
354              |                                  |
355              |                                  |
356              |                                  |
357              |                                  |
358              |                                  |
359            0 +----------------------------------+
360 @end group
361 @end example
362 @html
363 </CENTER>
364 @end html
365
366 In this project, the user stack is fixed in size, but in project 3 it
367 will be allowed to grow.  Traditionally, the size of the uninitialized
368 data segment can be adjusted with a system call, but you will not have
369 to implement this.
370
371 The code segment in Pintos starts at user virtual address
372 @t{0x08084000}, approximately 128 MB from the bottom of the address
373 space.  This value is specified in @bibref{SysV-i386} and has no deep
374 significance.
375
376 The linker sets the layout of a user program in memory, as directed by a
377 ``linker script'' that tells it the names and locations of the various
378 program segments.  You can learn more about linker scripts by reading
379 the ``Scripts'' chapter in the linker manual, accessible via @samp{info
380 ld}.
381
382 To view the layout of a particular executable, run @command{objdump}
383 (80@var{x}86) or @command{i386-elf-objdump} (SPARC) with the @option{-p}
384 option.
385
386 @node Accessing User Memory
387 @subsection Accessing User Memory
388
389 As part of a system
390 call, the kernel must often access memory through pointers provided by a user
391 program.  The kernel must be very careful about doing so, because
392 the user can pass a null pointer, a pointer to
393 unmapped virtual memory, or a pointer to kernel virtual address space
394 (above @code{PHYS_BASE}).  All of these types of invalid pointers must
395 be rejected without harm to the kernel or other running processes, by
396 terminating the offending process and freeing its resources.
397
398 There are at least two reasonable ways to do this correctly.  The
399 first method is to verify
400 the validity of a user-provided pointer, then dereference it.  If you
401 choose this route, you'll want to look at the functions in
402 @file{userprog/pagedir.c} and in @file{threads/vaddr.h}.  This is the
403 simplest way to handle user memory access.
404
405 The second method is to check only that a user
406 pointer points below @code{PHYS_BASE}, then dereference it.
407 An invalid user pointer will cause a ``page fault'' that you can
408 handle by modifying the code for @func{page_fault} in
409 @file{userprog/exception.c}.  This technique is normally faster
410 because it takes advantage of the processor's MMU, so it tends to be
411 used in real kernels (including Linux).
412
413 In either case, you need to make sure not to ``leak'' resources.  For
414 example, suppose that your system call has acquired a lock or
415 allocated memory with @func{malloc}.  If you encounter an invalid user pointer
416 afterward, you must still be sure to release the lock or free the page
417 of memory.  If you choose to verify user pointers before dereferencing
418 them, this should be straightforward.  It's more difficult to handle
419 if an invalid pointer causes a page fault,
420 because there's no way to return an error code from a memory access.
421 Therefore, for those who want to try the latter technique, we'll
422 provide a little bit of helpful code:
423
424 @verbatim
425 /* Reads a byte at user virtual address UADDR.
426    UADDR must be below PHYS_BASE.
427    Returns the byte value if successful, -1 if a segfault
428    occurred. */
429 static int
430 get_user (const uint8_t *uaddr)
431 {
432   int result;
433   asm ("movl $1f, %0; movzbl %1, %0; 1:"
434        : "=&a" (result) : "m" (*uaddr));
435   return result;
436 }
437  
438 /* Writes BYTE to user address UDST.
439    UDST must be below PHYS_BASE.
440    Returns true if successful, false if a segfault occurred. */
441 static bool
442 put_user (uint8_t *udst, uint8_t byte)
443 {
444   int error_code;
445   asm ("movl $1f, %0; movb %b2, %1; 1:"
446        : "=&a" (error_code), "=m" (*udst) : "q" (byte));
447   return error_code != -1;
448 }
449 @end verbatim
450
451 Each of these functions assumes that the user address has already been
452 verified to be below @code{PHYS_BASE}.  They also assume that you've
453 modified @func{page_fault} so that a page fault in the kernel merely
454 sets @code{eax} to @t{0xffffffff} and copies its former value
455 into @code{eip}.
456
457 @node Project 2 Suggested Order of Implementation
458 @section Suggested Order of Implementation
459
460 We suggest first implementing the following, which can happen in
461 parallel:
462
463 @itemize
464 @item
465 Argument passing (@pxref{Argument Passing}).  Every user program will
466 page fault immediately until argument passing is implemented.
467
468 For now, you may simply wish to change
469 @example
470 *esp = PHYS_BASE;
471 @end example
472 @noindent to
473 @example
474 *esp = PHYS_BASE - 12;
475 @end example
476 in @func{setup_stack}.  That will work for any test program that doesn't
477 examine its arguments, although its name will be printed as
478 @code{(null)}.
479
480 Until you implement argument passing, you should only run programs
481 without passing command-line arguments.  Attempting to pass arguments to
482 a program will include those arguments in the name of the program, which
483 will probably fail.
484
485 @item
486 User memory access (@pxref{Accessing User Memory}).  All system calls
487 need to read user memory.  Few system calls need to write to user
488 memory.
489
490 @item
491 System call infrastructure (@pxref{System Calls}).  Implement enough
492 code to read the system call number from the user stack and dispatch to
493 a handler based on it.
494
495 @item
496 The @code{exit} system call.  Every user program that finishes in the
497 normal way calls @code{exit}.  Even a program that returns from
498 @func{main} calls @code{exit} indirectly (see @func{_start} in
499 @file{lib/user/entry.c}).
500
501 @item
502 The @code{write} system call for writing to fd 1, the system console.
503 All of our test programs write to the console (the user process version
504 of @func{printf} is implemented this way), so they will all malfunction
505 until @code{write} is available.
506
507 @item
508 For now, change @func{process_wait} to an infinite loop (one that waits
509 forever).  The provided implementation returns immediately, so Pintos
510 will power off before any processes actually get to run.  You will
511 eventually need to provide a correct implementation.
512 @end itemize
513
514 After the above are implemented, user processes should work minimally.
515 At the very least, they can write to the console and exit correctly.
516 You can then refine your implementation so that some of the tests start
517 to pass.
518
519 @node Project 2 Requirements
520 @section Requirements
521
522 @menu
523 * Project 2 Design Document::   
524 * Process Termination Messages::  
525 * Argument Passing::            
526 * System Calls::                
527 * Denying Writes to Executables::  
528 @end menu
529
530 @node Project 2 Design Document
531 @subsection Design Document
532
533 Before you turn in your project, you must copy @uref{userprog.tmpl, ,
534 the project 2 design document template} into your source tree under the
535 name @file{pintos/src/userprog/DESIGNDOC} and fill it in.  We recommend
536 that you read the design document template before you start working on
537 the project.  @xref{Project Documentation}, for a sample design document
538 that goes along with a fictitious project.
539
540 @node Process Termination Messages
541 @subsection Process Termination Messages
542
543 Whenever a user process terminates, because it called @code{exit}
544 or for any other reason, print the process's name
545 and exit code, formatted as if printed by @code{printf ("%s:
546 exit(%d)\n", @dots{});}.  The name printed should be the full name
547 passed to @func{process_execute}, omitting command-line arguments.
548 Do not print these messages when a kernel thread that is not a user
549 process terminates, or
550 when the @code{halt} system call is invoked.  The message is optional
551 when a process fails to load.
552
553 Aside from this, don't print any other
554 messages that Pintos as provided doesn't already print.  You may find
555 extra messages useful during debugging, but they will confuse the
556 grading scripts and thus lower your score.
557
558 @node Argument Passing
559 @subsection Argument Passing
560
561 Currently, @func{process_execute} does not support passing arguments to
562 new processes.  Implement this functionality, by extending
563 @func{process_execute} so that instead of simply taking a program file
564 name as its argument, it divides it into words at spaces.  The first
565 word is the program name, the second word is the first argument, and so
566 on.  That is, @code{process_execute("grep foo bar")} should run
567 @command{grep} passing two arguments @code{foo} and @code{bar}.
568
569 Within a command line, multiple spaces are equivalent to a single
570 space, so that @code{process_execute("grep @w{ }foo @w{ }@w{ }bar")}
571 is equivalent to our original example.  You can impose a reasonable
572 limit on the length of the command line arguments.  For example, you
573 could limit the arguments to those that will fit in a single page (4
574 kB).  (There is an unrelated limit of 128 bytes on command-line
575 arguments that the @command{pintos} utility can pass to the kernel.)
576
577 You can parse argument strings any way you like.  If you're lost,
578 look at @func{strtok_r}, prototyped in @file{lib/string.h} and
579 implemented with thorough comments in @file{lib/string.c}.  You can
580 find more about it by looking at the man page (run @code{man strtok_r}
581 at the prompt).
582
583 @xref{Program Startup Details}, for information on exactly how you
584 need to set up the stack.
585
586 @node System Calls
587 @subsection System Calls
588
589 Implement the system call handler in @file{userprog/syscall.c}.  The
590 skeleton implementation we provide ``handles'' system calls by
591 terminating the process.  It will need to retrieve the system call
592 number, then any system call arguments, and carry out appropriate actions.
593
594 Implement the following system calls.  The prototypes listed are those
595 seen by a user program that includes @file{lib/user/syscall.h}.  (This
596 header, and all others in @file{lib/user}, are for use by user
597 programs only.)  System call numbers for each system call are defined in
598 @file{lib/syscall-nr.h}:
599
600 @deftypefn {System Call} void halt (void)
601 Terminates Pintos by calling @func{power_off} (declared in
602 @file{threads/init.h}).  This should be seldom used, because you lose
603 some information about possible deadlock situations, etc.
604 @end deftypefn
605
606 @deftypefn {System Call} void exit (int @var{status})
607 Terminates the current user program, returning @var{status} to the
608 kernel.  If the process's parent @code{wait}s for it (see below), this
609 is the status
610 that will be returned.  Conventionally, a @var{status} of 0 indicates
611 success and nonzero values indicate errors.
612 @end deftypefn
613
614 @deftypefn {System Call} pid_t exec (const char *@var{cmd_line})
615 Runs the executable whose name is given in @var{cmd_line}, passing any
616 given arguments, and returns the new process's program id (pid).  Must
617 return pid -1, which otherwise should not be a valid pid, if
618 the program cannot load or run for any reason.
619 Thus, the parent process cannot return from the @code{exec} until it
620 knows whether the child process successfully loaded its executable.
621 You must use appropriate synchronization to ensure this.
622 @end deftypefn
623
624 @deftypefn {System Call} int wait (pid_t @var{pid})
625 Waits for a child process @var{pid} and retrieves the child's exit status.
626
627 If @var{pid} is still alive, waits until it terminates.  Then, returns
628 the status that @var{pid} passed to @code{exit}.  If @var{pid} did not
629 call @code{exit()}, but was terminated by the kernel (e.g.@: killed
630 due to an exception), @code{wait(pid)} must return -1.  It is perfectly
631 legal for a parent process to wait for child processes that have already
632 terminated by the time the parent calls @code{wait}, but the kernel must
633 still allow the parent to retrieve its child's exit status, or learn
634 that the child was terminated by the kernel.
635
636 @code{wait} must fail and return -1 immediately if any of the
637 following conditions is true:
638 @itemize @bullet
639 @item
640 @var{pid} does not refer to a direct child of the calling process.
641 @var{pid} is a direct child of the calling process if and
642 only if the calling process received @var{pid} as a return value
643 from a successful call to @code{exec}.
644
645 Note that children are not inherited: if @var{A} spawns child @var{B}
646 and @var{B} spawns child process @var{C}, then @var{A} cannot wait for
647 @var{C}, even if @var{B} is dead.  A call to @code{wait(C)} by process
648 @var{A} must fail.  Similarly, orphaned processes are not assigned to
649 a new parent if their parent process exits before they do.
650
651 @item
652 The process that calls @code{wait} has already called @code{wait} on
653 @var{pid}.  That is, a process may wait for any given child at most
654 once.
655 @end itemize
656
657 Processes may spawn any number of children, wait for them in any order,
658 and may even exit without having waited for some or all of their children.
659 Your design should consider all the ways in which waits can occur.
660 All of a process's resources, including its @struct{thread}, must be
661 freed whether its parent ever waits for it or not, and regardless of
662 whether the child exits before or after its parent.
663
664 You must ensure that Pintos does not terminate until the initial
665 process exits.  The supplied Pintos code tries to do this by calling
666 @func{process_wait} (in @file{userprog/process.c}) from @func{main}
667 (in @file{threads/init.c}).  We suggest that you implement
668 @func{process_wait} according to the comment at the top of the
669 function and then implement the @code{wait} system call in terms of
670 @func{process_wait}.
671
672 Implementing this system call requires considerably more work than any
673 of the rest.
674 @end deftypefn
675
676 @deftypefn {System Call} bool create (const char *@var{file}, unsigned @var{initial_size})
677 Creates a new file called @var{file} initially @var{initial_size} bytes
678 in size.  Returns true if successful, false otherwise.
679 Creating a new file does not open it: opening the new file is a
680 separate operation which would require a @code{open} system call.
681 @end deftypefn
682
683 @deftypefn {System Call} bool remove (const char *@var{file})
684 Deletes the file called @var{file}.  Returns true if successful, false
685 otherwise.
686 A file may be removed regardless of whether it is open or closed, and
687 removing an open file does not close it.  @xref{Removing an Open
688 File}, for details.
689 @end deftypefn
690
691 @deftypefn {System Call} int open (const char *@var{file})
692 Opens the file called @var{file}.  Returns a nonnegative integer handle
693 called a ``file descriptor'' (fd), or -1 if the file could not be
694 opened.  
695
696 File descriptors numbered 0 and 1 are reserved for the console: fd 0
697 (@code{STDIN_FILENO}) is standard input, fd 1 (@code{STDOUT_FILENO}) is
698 standard output.  The @code{open} system call will never return either
699 of these file descriptors, which are valid as system call arguments only
700 as explicitly described below.
701
702 Each process has an independent set of file descriptors.  File
703 descriptors are not inherited by child processes.
704
705 When a single file is opened more than once, whether by a single
706 process or different processes, each @code{open} returns a new file
707 descriptor.  Different file descriptors for a single file are closed
708 independently in separate calls to @code{close} and they do not share
709 a file position.
710 @end deftypefn
711
712 @deftypefn {System Call} int filesize (int @var{fd})
713 Returns the size, in bytes, of the file open as @var{fd}.
714 @end deftypefn
715
716 @deftypefn {System Call} int read (int @var{fd}, void *@var{buffer}, unsigned @var{size})
717 Reads @var{size} bytes from the file open as @var{fd} into
718 @var{buffer}.  Returns the number of bytes actually read (0 at end of
719 file), or -1 if the file could not be read (due to a condition other
720 than end of file).  Fd 0 reads from the keyboard using
721 @func{input_getc}.
722 @end deftypefn
723
724 @deftypefn {System Call} int write (int @var{fd}, const void *@var{buffer}, unsigned @var{size})
725 Writes @var{size} bytes from @var{buffer} to the open file @var{fd}.
726 Returns the number of bytes actually written, which may be less than
727 @var{size} if some bytes could not be written.
728
729 Writing past end-of-file would normally extend the file, but file growth
730 is not implemented by the basic file system.  The expected behavior is
731 to write as many bytes as possible up to end-of-file and return the
732 actual number written, or 0 if no bytes could be written at all.
733
734 Fd 1 writes to the console.  Your code to write to the console should
735 write all of @var{buffer} in one call to @func{putbuf}, at least as
736 long as @var{size} is not bigger than a few hundred bytes.  (It is
737 reasonable to break up larger buffers.)  Otherwise,
738 lines of text output by different processes may end up interleaved on
739 the console, confusing both human readers and our grading scripts.
740 @end deftypefn
741
742 @deftypefn {System Call} void seek (int @var{fd}, unsigned @var{position})
743 Changes the next byte to be read or written in open file @var{fd} to
744 @var{position}, expressed in bytes from the beginning of the file.
745 (Thus, a @var{position} of 0 is the file's start.)
746
747 A seek past the current end of a file is not an error.  A later read
748 obtains 0 bytes, indicating end of file.  A later write extends the
749 file, filling any unwritten gap with zeros.  (However, in Pintos files
750 have a fixed length until project 4 is complete, so writes past end of
751 file will return an error.)  These semantics are implemented in the
752 file system and do not require any special effort in system call
753 implementation.
754 @end deftypefn
755
756 @deftypefn {System Call} unsigned tell (int @var{fd})
757 Returns the position of the next byte to be read or written in open
758 file @var{fd}, expressed in bytes from the beginning of the file.
759 @end deftypefn
760
761 @deftypefn {System Call} void close (int @var{fd})
762 Closes file descriptor @var{fd}.  
763 Exiting or terminating a process implicitly closes all its open file
764 descriptors, as if by calling this function for each one.
765 @end deftypefn
766
767 The file defines other syscalls.  Ignore them for now.  You will
768 implement some of them in project 3 and the rest in project 4, so be
769 sure to design your system with extensibility in mind.
770
771 To implement syscalls, you need to provide ways to read and write data
772 in user virtual address space.
773 You need this ability before you can
774 even obtain the system call number, because the system call number is
775 on the user's stack in the user's virtual address space.
776 This can be a bit tricky: what if the user provides an invalid
777 pointer, a pointer into kernel memory, or a block
778 partially in one of those regions?  You should handle these cases by
779 terminating the user process.  We recommend
780 writing and testing this code before implementing any other system
781 call functionality.  @xref{Accessing User Memory}, for more information.
782
783 You must synchronize system calls so that
784 any number of user processes can make them at once.  In particular, it
785 is not safe to call into the file system code provided in the
786 @file{filesys} directory from multiple threads at once.  Your system
787 call implementation must treat the file system code as a critical
788 section.  Don't forget
789 that @func{process_execute} also accesses files.  For now, we
790 recommend against modifying code in the @file{filesys} directory.
791
792 We have provided you a user-level function for each system call in
793 @file{lib/user/syscall.c}.  These provide a way for user processes to
794 invoke each system call from a C program.  Each uses a little inline
795 assembly code to invoke the system call and (if appropriate) returns the
796 system call's return value.
797
798 When you're done with this part, and forevermore, Pintos should be
799 bulletproof.  Nothing that a user program can do should ever cause the
800 OS to crash, panic, fail an assertion, or otherwise malfunction.  It is
801 important to emphasize this point: our tests will try to break your
802 system calls in many, many ways.  You need to think of all the corner
803 cases and handle them.  The sole way a user program should be able to
804 cause the OS to halt is by invoking the @code{halt} system call.
805
806 If a system call is passed an invalid argument, acceptable options
807 include returning an error value (for those calls that return a
808 value), returning an undefined value, or terminating the process.
809
810 @xref{System Call Details}, for details on how system calls work.
811
812 @node Denying Writes to Executables
813 @subsection Denying Writes to Executables
814
815 Add code to deny writes to files in use as executables.  Many OSes do
816 this because of the unpredictable results if a process tried to run code
817 that was in the midst of being changed on disk.  This is especially
818 important once virtual memory is implemented in project 3, but it can't
819 hurt even now.
820
821 You can use @func{file_deny_write} to prevent writes to an open file.
822 Calling @func{file_allow_write} on the file will re-enable them (unless
823 the file is denied writes by another opener).  Closing a file will also
824 re-enable writes.  Thus, to deny writes to a process's executable, you
825 must keep it open as long as the process is still running.
826
827 @node Project 2 FAQ
828 @section FAQ
829
830 @table @asis
831 @item How much code will I need to write?
832
833 Here's a summary of our reference solution, produced by the
834 @command{diffstat} program.  The final row gives total lines inserted
835 and deleted; a changed line counts as both an insertion and a deletion.
836
837 The reference solution represents just one possible solution.  Many
838 other solutions are also possible and many of those differ greatly from
839 the reference solution.  Some excellent solutions may not modify all the
840 files modified by the reference solution, and some may modify files not
841 modified by the reference solution.
842
843 @verbatim
844  threads/thread.c     |   13 
845  threads/thread.h     |   26 +
846  userprog/exception.c |    8 
847  userprog/process.c   |  247 ++++++++++++++--
848  userprog/syscall.c   |  468 ++++++++++++++++++++++++++++++-
849  userprog/syscall.h   |    1 
850  6 files changed, 725 insertions(+), 38 deletions(-)
851 @end verbatim
852
853 @item The kernel always panics when I run @code{pintos -p @var{file} -- -q}.
854
855 Did you format the disk (with @samp{pintos -f})?
856
857 Is your file name too long?  The file system limits file names to 14
858 characters.  A command like @samp{pintos -p ../../examples/echo -- -q}
859 will exceed the limit.  Use @samp{pintos -p ../../examples/echo -a echo
860 -- -q} to put the file under the name @file{echo} instead.
861
862 Is the file system full?
863
864 Does the file system already contain 16 files?  The base Pintos file
865 system has a 16-file limit.
866
867 The file system may be so fragmented that there's not enough contiguous
868 space for your file.
869
870 @item When I run @code{pintos -p ../file --}, @file{file} isn't copied.
871
872 Files are written under the name you refer to them, by default, so in
873 this case the file copied in would be named @file{../file}.  You
874 probably want to run @code{pintos -p ../file -a file --} instead.
875
876 @item All my user programs die with page faults.
877
878 This will happen if you haven't implemented argument passing
879 (or haven't done so correctly).  The basic C library for user programs tries
880 to read @var{argc} and @var{argv} off the stack.  If the stack
881 isn't properly set up, this causes a page fault.
882
883 @item All my user programs die with @code{system call!}
884
885 You'll have to implement system calls before you see anything else.
886 Every reasonable program tries to make at least one system call
887 (@func{exit}) and most programs make more than that.  Notably,
888 @func{printf} invokes the @code{write} system call.  The default system
889 call handler just prints @samp{system call!} and terminates the program.
890 Until then, you can use @func{hex_dump} to convince yourself that
891 argument passing is implemented correctly (@pxref{Program Startup Details}).
892
893 @item How can I disassemble user programs?
894
895 The @command{objdump} (80@var{x}86) or @command{i386-elf-objdump}
896 (SPARC) utility can disassemble entire user
897 programs or object files.  Invoke it as @code{objdump -d
898 @var{file}}.  You can use GDB's
899 @code{disassemble} command to disassemble individual functions
900 (@pxref{GDB}).
901
902 @item Why do many C include files not work in Pintos programs?
903 @itemx Can I use lib@var{foo} in my Pintos programs?
904
905 The C library we provide is very limited.  It does not include many of
906 the features that are expected of a real operating system's C library.
907 The C library must be built specifically for the operating system (and
908 architecture), since it must make system calls for I/O and memory
909 allocation.  (Not all functions do, of course, but usually the library
910 is compiled as a unit.)
911
912 The chances are good that the library you want uses parts of the C library
913 that Pintos doesn't implement.  It will probably take at least some
914 porting effort to make it work under Pintos.  Notably, the Pintos
915 user program C library does not have a @func{malloc} implementation.
916
917 @item How do I compile new user programs?
918
919 Modify @file{src/examples/Makefile}, then run @command{make}.
920
921 @item Can I run user programs under a debugger?
922
923 Yes, with some limitations.  @xref{Debugging User Programs}.
924
925 @item What's the difference between @code{tid_t} and @code{pid_t}?
926
927 A @code{tid_t} identifies a kernel thread, which may have a user
928 process running in it (if created with @func{process_execute}) or not
929 (if created with @func{thread_create}).  It is a data type used only
930 in the kernel.
931
932 A @code{pid_t} identifies a user process.  It is used by user
933 processes and the kernel in the @code{exec} and @code{wait} system
934 calls.
935
936 You can choose whatever suitable types you like for @code{tid_t} and
937 @code{pid_t}.  By default, they're both @code{int}.  You can make them
938 a one-to-one mapping, so that the same values in both identify the
939 same process, or you can use a more complex mapping.  It's up to you.
940 @end table
941
942 @menu
943 * Argument Passing FAQ::        
944 * System Calls FAQ::            
945 @end menu
946
947 @node Argument Passing FAQ
948 @subsection Argument Passing FAQ
949
950 @table @asis
951 @item Isn't the top of stack in kernel virtual memory?
952
953 The top of stack is at @code{PHYS_BASE}, typically @t{0xc0000000}, which
954 is also where kernel virtual memory starts.
955 But before the processor pushes data on the stack, it decrements the stack
956 pointer.  Thus, the first (4-byte) value pushed on the stack
957 will be at address @t{0xbffffffc}.
958
959 @item Is @code{PHYS_BASE} fixed?
960
961 No.  You should be able to support @code{PHYS_BASE} values that are
962 any multiple of @t{0x10000000} from @t{0x80000000} to @t{0xf0000000},
963 simply via recompilation.
964 @end table
965
966 @node System Calls FAQ
967 @subsection System Calls FAQ
968
969 @table @asis
970 @item Can I just cast a @code{struct file *} to get a file descriptor?
971 @itemx Can I just cast a @code{struct thread *} to a @code{pid_t}?
972
973 You will have to make these design decisions yourself.
974 Most operating systems do distinguish between file
975 descriptors (or pids) and the addresses of their kernel data
976 structures.  You might want to give some thought as to why they do so
977 before committing yourself.
978
979 @item Can I set a maximum number of open files per process?
980
981 It is better not to set an arbitrary limit.  You may impose a limit of
982 128 open files per process, if necessary.
983
984 @item What happens when an open file is removed?
985 @anchor{Removing an Open File}
986
987 You should implement the standard Unix semantics for files.  That is, when
988 a file is removed any process which has a file descriptor for that file
989 may continue to use that descriptor.  This means that
990 they can read and write from the file.  The file will not have a name,
991 and no other processes will be able to open it, but it will continue
992 to exist until all file descriptors referring to the file are closed
993 or the machine shuts down.
994
995 @item How can I run user programs that need more than 4 kB stack space?
996
997 You may modify the stack setup code to allocate more than one page of
998 stack space for each process.  In the next project, you will implement a
999 better solution.
1000
1001 @item What should happen if an @code{exec} fails midway through loading?
1002
1003 @code{exec} should return -1 if the child process fails to load for
1004 any reason.  This includes the case where the load fails part of the
1005 way through the process (e.g.@: where it runs out of memory in the
1006 @code{multi-oom} test).  Therefore, the parent process cannot return
1007 from the @code{exec} system call until it is established whether the
1008 load was successful or not.  The child must communicate this
1009 information to its parent using appropriate synchronization, such as a
1010 semaphore (@pxref{Semaphores}), to ensure that the information is
1011 communicated without race conditions.
1012 @end table
1013
1014 @node 80x86 Calling Convention
1015 @section 80@var{x}86 Calling Convention
1016
1017 This section summarizes important points of the convention used for
1018 normal function calls on 32-bit 80@var{x}86 implementations of Unix.
1019 Some details are omitted for brevity.  If you do want all the details,
1020 refer to @bibref{SysV-i386}.
1021
1022 The calling convention works like this:
1023
1024 @enumerate 1
1025 @item
1026 The caller pushes each of the function's arguments on the stack one by
1027 one, normally using the @code{PUSH} assembly language instruction.
1028 Arguments are pushed in right-to-left order.
1029
1030 The stack grows downward: each push decrements the stack pointer, then
1031 stores into the location it now points to, like the C expression
1032 @samp{*--sp = @var{value}}.
1033
1034 @item
1035 The caller pushes the address of its next instruction (the @dfn{return
1036 address}) on the stack and jumps to the first instruction of the callee.
1037 A single 80@var{x}86 instruction, @code{CALL}, does both.
1038
1039 @item
1040 The callee executes.  When it takes control, the stack pointer points to
1041 the return address, the first argument is just above it, the second
1042 argument is just above the first argument, and so on.
1043
1044 @item
1045 If the callee has a return value, it stores it into register @code{EAX}.
1046
1047 @item
1048 The callee returns by popping the return address from the stack and
1049 jumping to the location it specifies, using the 80@var{x}86 @code{RET}
1050 instruction.
1051
1052 @item
1053 The caller pops the arguments off the stack.
1054 @end enumerate
1055
1056 Consider a function @func{f} that takes three @code{int} arguments.
1057 This diagram shows a sample stack frame as seen by the callee at the
1058 beginning of step 3 above, supposing that @func{f} is invoked as
1059 @code{f(1, 2, 3)}.  The initial stack address is arbitrary:
1060
1061 @html
1062 <CENTER>
1063 @end html
1064 @example
1065                              +----------------+
1066                   0xbffffe7c |        3       |
1067                   0xbffffe78 |        2       |
1068                   0xbffffe74 |        1       |
1069 stack pointer --> 0xbffffe70 | return address |
1070                              +----------------+
1071 @end example
1072 @html
1073 </CENTER>
1074 @end html
1075
1076 @menu
1077 * Program Startup Details::     
1078 * System Call Details::         
1079 @end menu
1080
1081 @node Program Startup Details
1082 @subsection Program Startup Details
1083
1084 The Pintos C library for user programs designates @func{_start}, in
1085 @file{lib/user/entry.c}, as the entry point for user programs.  This
1086 function is a wrapper around @func{main} that calls @func{exit} if
1087 @func{main} returns:
1088
1089 @example
1090 void
1091 _start (int argc, char *argv[]) 
1092 @{
1093   exit (main (argc, argv));
1094 @}
1095 @end example
1096
1097 The kernel must put the arguments for the initial function on the stack
1098 before it allows the user program to begin executing.  The arguments are
1099 passed in the same way as the normal calling convention (@pxref{80x86
1100 Calling Convention}).
1101
1102 Consider how to handle arguments for the following example command:
1103 @samp{/bin/ls -l foo bar}.
1104 First, break the command into words: @samp{/bin/ls},
1105 @samp{-l}, @samp{foo}, @samp{bar}.  Place the words at the top of the
1106 stack.  Order doesn't matter, because they will be referenced through
1107 pointers.
1108
1109 Then, push the address of each string plus a null pointer sentinel, on
1110 the stack, in right-to-left order.  These are the elements of
1111 @code{argv}.  The null pointer sentinel ensures that @code{argv[argc]}
1112 is a null pointer, as required by the C standard.  The order ensures
1113 that @code{argv[0]} is at the lowest virtual address.  Word-aligned
1114 accesses are faster than unaligned accesses, so for best performance
1115 round the stack pointer down to a multiple of 4 before the first push.
1116
1117 Then, push @code{argv} (the address of @code{argv[0]}) and @code{argc},
1118 in that order.  Finally, push a fake ``return address'': although the
1119 entry function will never return, its stack frame must have the same
1120 structure as any other.
1121
1122 The table below shows the state of the stack and the relevant registers
1123 right before the beginning of the user program, assuming
1124 @code{PHYS_BASE} is @t{0xc0000000}:
1125
1126 @html
1127 <CENTER>
1128 @end html
1129 @multitable {@t{0xbfffffff}} {return address} {@t{/bin/ls\0}} {@code{void (*) ()}}
1130 @item Address @tab Name @tab Data @tab Type
1131 @item @t{0xbffffffc} @tab @code{argv[3][@dots{}]} @tab @samp{bar\0} @tab @code{char[4]}
1132 @item @t{0xbffffff8} @tab @code{argv[2][@dots{}]} @tab @samp{foo\0} @tab @code{char[4]}
1133 @item @t{0xbffffff5} @tab @code{argv[1][@dots{}]} @tab @samp{-l\0} @tab @code{char[3]}
1134 @item @t{0xbfffffed} @tab @code{argv[0][@dots{}]} @tab @samp{/bin/ls\0} @tab @code{char[8]}
1135 @item @t{0xbfffffec} @tab word-align @tab 0 @tab @code{uint8_t}
1136 @item @t{0xbfffffe8} @tab @code{argv[4]} @tab @t{0} @tab @code{char *}
1137 @item @t{0xbfffffe4} @tab @code{argv[3]} @tab @t{0xbffffffc} @tab @code{char *}
1138 @item @t{0xbfffffe0} @tab @code{argv[2]} @tab @t{0xbffffff8} @tab @code{char *}
1139 @item @t{0xbfffffdc} @tab @code{argv[1]} @tab @t{0xbffffff5} @tab @code{char *}
1140 @item @t{0xbfffffd8} @tab @code{argv[0]} @tab @t{0xbfffffed} @tab @code{char *}
1141 @item @t{0xbfffffd4} @tab @code{argv} @tab @t{0xbfffffd8} @tab @code{char **}
1142 @item @t{0xbfffffd0} @tab @code{argc} @tab 4 @tab @code{int}
1143 @item @t{0xbfffffcc} @tab return address @tab 0 @tab @code{void (*) ()}
1144 @end multitable
1145 @html
1146 </CENTER>
1147 @end html
1148
1149 In this example, the stack pointer would be initialized to
1150 @t{0xbfffffcc}.
1151
1152 As shown above, your code should start the stack at the very top of
1153 the user virtual address space, in the page just below virtual address
1154 @code{PHYS_BASE} (defined in @file{threads/vaddr.h}).
1155
1156 You may find the non-standard @func{hex_dump} function, declared in
1157 @file{<stdio.h>}, useful for debugging your argument passing code.
1158 Here's what it would show in the above example:
1159
1160 @verbatim
1161 bfffffc0                                      00 00 00 00 |            ....|
1162 bfffffd0  04 00 00 00 d8 ff ff bf-ed ff ff bf f5 ff ff bf |................|
1163 bfffffe0  f8 ff ff bf fc ff ff bf-00 00 00 00 00 2f 62 69 |............./bi|
1164 bffffff0  6e 2f 6c 73 00 2d 6c 00-66 6f 6f 00 62 61 72 00 |n/ls.-l.foo.bar.|
1165 @end verbatim
1166
1167 @node System Call Details
1168 @subsection System Call Details
1169
1170 The first project already dealt with one way that the operating system
1171 can regain control from a user program: interrupts from timers and I/O
1172 devices.  These are ``external'' interrupts, because they are caused
1173 by entities outside the CPU (@pxref{External Interrupt Handling}).
1174
1175 The operating system also deals with software exceptions, which are
1176 events that occur in program code (@pxref{Internal Interrupt
1177 Handling}).  These can be errors such as a page fault or division by
1178 zero.  Exceptions are also the means by which a user program
1179 can request services (``system calls'') from the operating system.
1180
1181 In the 80@var{x}86 architecture, the @samp{int} instruction is the
1182 most commonly used means for invoking system calls.  This instruction
1183 is handled in the same way as other software exceptions.  In Pintos,
1184 user programs invoke @samp{int $0x30} to make a system call.  The
1185 system call number and any additional arguments are expected to be
1186 pushed on the stack in the normal fashion before invoking the
1187 interrupt (@pxref{80x86 Calling Convention}).
1188
1189 Thus, when the system call handler @func{syscall_handler} gets control,
1190 the system call number is in the 32-bit word at the caller's stack
1191 pointer, the first argument is in the 32-bit word at the next higher
1192 address, and so on.  The caller's stack pointer is accessible to
1193 @func{syscall_handler} as the @samp{esp} member of the
1194 @struct{intr_frame} passed to it.  (@struct{intr_frame} is on the kernel
1195 stack.)
1196
1197 The 80@var{x}86 convention for function return values is to place them
1198 in the @code{EAX} register.  System calls that return a value can do
1199 so by modifying the @samp{eax} member of @struct{intr_frame}.
1200
1201 You should try to avoid writing large amounts of repetitive code for
1202 implementing system calls.  Each system call argument, whether an
1203 integer or a pointer, takes up 4 bytes on the stack.  You should be able
1204 to take advantage of this to avoid writing much near-identical code for
1205 retrieving each system call's arguments from the stack.