1 PROJECT 2 GRADING ADVICE
2 ========================
4 This file contains advice for grading project 2. General advice for
5 Pintos grading is in README, which you should read first.
12 Most correct solutions don't introduce any new data structures for
15 If any global variables are introduced, be suspicious about the
16 possibility for race conditions.
20 The "Program Startup Details" section in the User Programs chapter
21 of the Pintos manual describes what needs to be done.
23 There are two main ways to put argv[] in the correct order:
25 - Many solutions use strtok_r() to divide the arguments into
26 space-separated strings, storing a pointer to each argument
27 in a temporary storage area, then push each pointer on the
28 stack in reverse order.
30 - Another approach is to push the arguments obtained by
31 strtok_r() on the user stack directly, then reverse their
32 order when finished. This is what the sample solution does.
34 Students must specify how they avoid overflow:
36 - One acceptable approach is to check for overflow just before
37 pushing each item on the stack.
39 - Another acceptable approach is to make two passes. In the
40 first pass, calculate how many bytes of stack space are
41 required. Abort at this point if the stack would overflow.
42 Then, in the second pass, actually set up the stack.
44 - A third acceptable approach is to allocate additional stack
45 pages as the currently allocate page or pages are exhausted.
46 If this is done, verify that the case where no more memory
47 is available is correctly handled (by returning an error and
48 ensuring that the pages already allocated are freed).
50 Few groups choose this approach.
52 - Some students assume that any command line under 4,096 bytes
53 long will fit. This is wrong: some space is required for
54 the pointers in argv[], as well as a little extra for other
55 data that goes on the stack and some space for the user
56 process's use as well.
58 - Generalizing the previous approach, some students set some
59 other fixed limit on command-line length in bytes. Usually
60 they don't properly consider the consequences. Every two
61 bytes in a command line can require four bytes for a pointer
62 in argv[], as in a command line that consists of alternating
63 space and non-space characters. Thus, N bytes of
64 command-line arguments can require N + 4(N / 2) = 3N bytes
65 of stack space. Setting 3N = 4,096 we obtain N = 1,365.
66 Thus, any solution that sets a fixed cap on command-line
67 length greater than 1,365 is incorrect. Preferably, any
68 fixed limit should be significantly less than that.
70 - Some students believe that there is a 128-byte limit on the
71 length of a command line. This is wrong: the 128-byte limit
72 only applies to the "pintos" utility's command line. It
73 does not apply to the command line passed to the "exec"
76 - Some groups limit the number of command line arguments to a
77 fixed value. There's nothing wrong with that as long as
78 it's sufficiently large, e.g. 512.
80 One common fallacy is an assumption that each string must be
81 word-aligned for performance. This is not true. It's okay if
82 they align strings, because it's harmless, but stating that it
83 improves performance should incur a small deduction.
87 strtok() uses a static object to hold the starting position for
88 the next token. Thus, it isn't safe for concurrent use in
89 different threads (the problem here) or even for nested use within
92 strtok_r() solves the problem by requiring the caller to provide
93 storage for the starting position for the next token.
97 - Some students believe that strtok_r() does not modify the
98 string it tokenizes whereas strtok() does. This is wrong:
99 both functions modify the string that they tokenize.
101 - Some students think strtok() uses a "static buffer" for
102 parsing. This is wrong: it modifies the string provided and
103 stores a pointer into it statically.
107 Some correct answers:
109 - Increased flexibility: a variety of shells can accept
110 varying syntaxes without any need to change the kernel.
112 - Simplifies the kernel and improves its security: a simpler
113 kernel is a kernel less likely to have important bugs or
114 security holes. This is especially true given the
115 complicated parsing rules of real-world shells.
119 - Saves time and disk space: doing parsing in user space or
120 kernel space doesn't have a strong time or space trade-off,
121 but some students think so.
123 - Relative paths: some students think that relative paths are
124 implemented by the shell, but this is wrong.
126 - Fewer context switches: where parsing is done has no effect
127 on the number of context switches required to start a
130 - Policy enforcement: some students think that the shell is in
131 charge of enforcing system security policies, but this is
134 Check the submitted code, by hand, for the following:
136 1. That the code used for argument passing is readable. This is
137 probably near the end of userprog/process.c, in or near
138 setup_stack(). In particular, many stack "push" operations are
139 required, so the code to do this should either be simple
140 (e.g. "*--p = something;") or, if it is more complicated,
141 abstracted into a function or set of functions.
148 This question has a pretty big answer, because system calls need
149 quite a few data structures. The guidelines for B1 are therefore
150 broken down into B1(i) through B1(iv), below, to make them easier
155 A global lock or semaphore for file system synchronization is
158 /* Serializes file system operations. */
159 static struct lock fs_lock;
163 Some mechanism for tracking file descriptors is needed. There are
164 three common variants (see B2 for more on this topic):
166 - Per-thread list: adds a list to struct thread, like so:
168 struct list fds; /* List of file descriptors. */
170 Each member of the list includes at least a file and a fd
173 /* A file descriptor, for binding a file handle to a file. */
174 struct file_descriptor
176 struct list_elem elem; /* List element. */
177 struct file *file; /* File. */
178 int handle; /* File handle. */
181 This case also requires a way to come up with unique file
182 descriptors. The simplest and best way is to add a counter
183 to struct thread, e.g.:
185 int next_handle; /* Next handle value. */
187 Another alternative is to use a global counter, but this
188 requires adding a lock as well. (It's possible to use the
189 global file system lock or some other lock for this, but I
190 haven't seen that done in practice.) Deduct points if
191 synchronization is omitted:
193 static int next_fd = 2; /* Next file descriptor. */
194 static struct lock fd_lock; /* Protects next_fd. */
196 - Per-thread array: adds an array of 128 elements to struct
197 thread (128 because the assignment states that as a minimum
200 struct file *fds[128];
202 Some solutions include some extra members to speed up
203 finding an empty slot.
205 - Global hash table: adds a global hash table that maps from a
206 descriptor number to a "struct file *". Check that there is
207 also a new hash_elem in struct thread in this case.
209 Some way to generate unique file descriptors is needed,
210 usually a global counter. A lock or other synchronization
213 The global data for this case looks something like this:
215 static struct hash fd_hash;
216 static int fd_next = 2;
217 static struct lock fd_lock;
219 The hash table elements look something like this:
221 struct file_descriptor
223 struct hash_elem hash_elem;
229 Notice the inclusion of the "owner" member, which ensures
230 that a fd can only be used by the process that opened it.
231 If there's no mechanism to ensure this, deduct points.
235 Data structures for implementing the "wait" system call are needed
236 (see B5 and B8 for more on this topic). Fundamentally, "wait"
237 requires communication between a process and its children, usually
238 implemented through shared data. The shared data might be added
239 to struct thread, but many solutions separate it into a separate
240 structure. At least the following must be shared between a parent
241 and each of its children:
243 - Child's exit status, so that "wait" can return it.
245 - Child's thread id, for "wait" to compare against its
248 - A way for the parent to block until the child dies (usually
251 - A way for the parent and child to tell whether the other is
252 already dead, in a race-free fashion (to ensure that their
253 shared data can be freed).
255 The sample solution uses a new "struct wait_status" for this
258 /* Tracks the completion of a process.
259 Reference held by both the parent, in its `children' list,
260 and by the child, in its `wait_status' pointer. */
263 struct list_elem elem; /* `children' list element. */
264 struct lock lock; /* Protects ref_cnt. */
265 int ref_cnt; /* 2=child and parent both alive,
266 1=either child or parent alive,
267 0=child and parent both dead. */
268 tid_t tid; /* Child thread id. */
269 int exit_code; /* Child exit code, if dead. */
270 struct semaphore dead; /* 1=child alive, 0=child dead. */
273 Of course, each thread needs a way to find the shared data for
274 each of its children and, if shared data is not stored in struct
275 thread, its own shared data as well. The sample solution adds a
276 pair of members to struct thread:
278 struct wait_status *wait_status; /* This process's completion state. */
279 struct list children; /* Completion status of children. */
281 Most solutions add an exit code member to struct thread, even if
282 there is an exit code member in a separate shared data structure.
287 Some data is needed to allow a process that calls "exec" to wait
288 until the new process completes loading. The sample solution, and
289 some student submissions, just add a new structure. A pointer to
290 the new structure is passed to the new thread as the "void *"
291 pointer argument to thread_create(). Here is the sample
292 solution's structure:
294 /* Data structure shared between process_execute() in the
295 invoking thread and execute_thread() in the newly invoked
299 const char *file_name; /* Program to load. */
300 struct semaphore load_done; /* "Up"ed when loading complete. */
301 struct wait_status *wait_status;/* Child process. */
302 bool success; /* Program successfully loaded? */
305 Many student submissions instead add members to struct thread to
306 do the same things, which is fine.
310 See B1(ii) above for information on the basic data structures used
311 for file descriptors. Part of the answer to this question might
314 Globally unique and per-process unique file descriptors are both
317 If a global counter is used to generate file descriptors, there
318 must be some mention of synchronization.
320 If an array totalling 512 bytes or more (e.g. 128 elements of
321 "int" or pointer type) is added to struct thread, then there must
322 be some mention that this is a large amount of data to add to
323 struct thread. See the "struct thread" section in the Reference
324 Guide chapter of the Pintos manual for explanation.
326 If the fd counter skips the first 3 fd values, with mention that
327 this is for stdin, stdout, and stderr, then it must also mention
328 that Pintos does not have stderr.
330 There seems to be some confusion about locking here among
331 students. No locking is necessary for per-thread data structures,
332 such as a thread-specific list of file descriptors. Locking is
333 required for data that might be concurrently accessed by multiple
336 There is no need for submissions to handle overflow of the counter
337 used for generating fds.
341 This question was badly phrased in previous quarters, so there's
342 no pool of good student answers to compare against.
344 The answer should say which of the techniques described in
345 "Accessing User Memory" in the assignment is used. It should
346 describe a few of the implementation details, such as interfaces
347 of functions used to read or write user memory.
349 A few students believe that writing to the "eax" member of struct
350 intr_frame is a form of writing to user memory. This is wrong:
351 struct intr_frame is in the kernel stack. Modifying its "eax"
352 member changes the value of the EAX register seen by the process
353 when a system call returns, not any kind of user memory.
355 Occasionally, a group extends the page fault-based method
356 described in the Pintos manual. The method described there has a
357 little bit of overhead in that it requires the EAX register to be
358 set up with the address of a recovery handler before accessing
359 memory. This is necessary for the page fault handler to know what
360 to do. An alternative without this overhead is to maintain a
361 table that associates EIP values of potentially faulting
362 instructions with their recovery handlers. This technique is used
363 in the Linux kernel and elsewhere to good effect.
367 In the first part of this question, students should address their
368 implementation. In the second part, they should address an ideal
369 implementation. They need to answer both parts, although the
370 answers may be very brief as long as they are correct.
372 An ideal implementation would only inspect as many page table
373 entries as aligned virtual pages spanned by the buffer. Both
374 2-byte and 4,096 buffers can span either 1 or 2 pages, so they
375 would require 1 or 2 checks.
377 Student implementations often check page table entries more often
378 than this. That's acceptable, within reason. For example, one
379 common student implementation checks the first byte and last byte
380 of the user memory block to be accessed, plus one byte spaced
381 every 4,096 bytes within the block. That's fine, although it
382 often makes a few more checks than absolutely necessary.
384 Implementations that always inspect every byte read or written are
385 not acceptable. Take off points.
387 Bizarrely, some students believe that checking a page table entry
388 every 4 bytes within a block is correct. It's not: it will fail,
389 for example, in the case of a 2-byte block spanning a pair of
390 virtual pages. If they check each *aligned* 4-byte region, then
391 it's correct, but then they're still doing 1,024 checks per page,
392 which is still unacceptable.
394 An implementation that uses page faults to detect bad user memory
395 accesses requires 0 page table inspections to copy any number of
396 bytes. An answer from this point of view is acceptable too.
398 Some students suggest that further improvements could be made by
399 page-aligning the buffers passed to the kernel. That's a
400 reasonable suggestion.
402 Some very confused students think that each of the bytes in a
403 4,096 user memory region can be on a separate page. Penalize
408 These questions really have to be graded together, because they
409 are so closely related. See B1(iii) above for information on the
410 basic data structures used for "wait".
412 A call to "wait" should not require disabling interrupts or
413 calling thread_block() by hand. Take off points.
415 Global locks, semaphores, etc. should not generally be used for
416 implementing "wait". Their use forces serialization of process
417 exit, and they are unnecessary. They are also, often, an
418 indication of an incorrect implementation.
420 Some students indicate that they actually implement the wrong
421 semantics: If C exits before P, then "wait" by P on C should
422 return the process's exit code, not -1 as these students say.
423 Take off points for this. (But it's strange that they would think
424 so, seeing as the tests for "wait" are pretty thorough.)
426 The "exit" and "wait" system calls should not have to search a
427 global list of all processes, because it is inefficient and, more
428 importantly, unnecessary given that it is so easy to keep a
429 per-thread list of children. Take off points.
431 The procedure for "wait" varies broadly based on the data
432 structures used. If shared data separate from struct thread are
433 used, the procedure is simpler:
435 - Find the child in the list of shared data structures. (If
436 none is found, return -1.)
438 - Wait for the child to die, by downing a semaphore in the
441 - Obtain the child's exit code from the shared data.
443 - Destroy the shared data structure and remove it from the
446 - Return the exit code.
448 A common variation on the above is to mark the shared data
449 structure as "used" instead of removing it from the list and
450 destroying it, then on subsequent "wait"s noticing that it is
451 already used, skipping the down of the semaphore, and returning
454 The procedure for "exit", in this case, is:
456 - Up the semaphore in the data shared with our parent process
457 (if any). In some kind of race-free way (such as using a
458 lock and a reference count or pair of boolean variables in
459 the shared data area), mark the shared data as unused by us
460 and free it if the parent is also dead.
462 - Iterate the list of children and, as in the previous step,
463 mark them as no longer used by us and free them if the child