CS61 Final 2014 Solutions
You have 180 minutes to complete this final, which contains 7 sections.
Do your work in the exam booklet. Use the backs of pages if you need to, but write something on the fronts to tell us where to look.
Some problems are harder than others and they are not ordered by difficulty; use your time wisely.
The exam is open book, open note, open computer. You may access the book, and your own notes in paper form. You may also use a computer or equivalent to your own class materials and public class materials. However, you may not access other materials except as explicitly allowed below, and you may not write programs to answer questions. Specifically:
- You may access a browser and a PDF reader.
- You may access your own notes and problem set code electronically.
- You may access an Internet site on which your own notes and problem set code are stored.
- You may access system manual pages (
man
). - You may access the cs61.seas.harvard.edu/wiki/2014 site, including scribe notes and our lecture and section notes.
But:
- You may not access Google or Wikipedia or anything else except as directly linked from the cs61.seas.harvard.edu/wiki/2014 site.
- You may not access Piazza or course videos.
- You may not run a C compiler, assembler, on-line disassembler, calculator, or anything similar. Simple reading applications only.
- You absolutely may not contact other humans via IM or anything like it.
- You may not access solutions from any previous exam, by paper or computer, except for those linked on the course wiki.
Any violations of this policy, or the spirit of this policy, are breaches of academic honesty and will be treated accordingly. Please appreciate our flexibility and behave honestly and honorably.
Name
Your name: |
____________________________________________________________________ |
Your student ID |
____________________________________________________________________ |
You must sign the following statement for us to grade the exam:
I have neither given nor received inappropriate help on this exam.
_________________________________________________________________ __________________________ Signature Date
0. Ground rules
Assume a 32-bit x86 architecture unless explicitly told otherwise. You may also assume that system calls never fail unexpectedly (e.g., no disk runs out of quota, no system call is unexpectedly interrupted).
Write your assumptions if a problem seems unclear, and write down your reasoning for partial credit.
1. Bit Tac Toe (15 points)
Brenda Bitdiddle is implementing tic-tac-toe using bitwise arithmetic. (If you’re unfamiliar with tic-tac-toe, see the appendix.) Her implementation starts like this:
typedef struct {
unsigned moves[2];
} tictactoe;
#define XS 0
#define OS 1
void tictactoe_init(tictactoe* b) {
b->moves[XS] = b->moves[OS] = 0;
}
static const unsigned ttt_values[3][3] = {
{ 0x001, 0x002, 0x004 },
{ 0x010, 0x020, 0x040 },
{ 0x100, 0x200, 0x400 }
};
` // Mark a move by player `p` at row `row` and column `col`. `
` // Return 0 on success; return –1 if position `row,col` has already been used. `
int tictactoe_move(tictactoe* b, int p, int row, int col) {
1.
assert(row >= 0 && row < 3 && col >= 0 && col < 3);
2.
assert(p == XS || p == OS);
3.
/* TODO: check for position reuse */
4.
b->moves[p] |= ttt_values[row][col];
5.
return 0;
}
Each position on the board is assigned a distinct bit.
QUESTION 1A (3 points). Brenda’s current code doesn’t check whether a move reuses a position. Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3.
3 points. Lots of people misinterpreted this to mean the player reused their own position and ignored the other player. That mistake is allowed (no points off).
if ((b->moves[XS] | b->moves[OS]) & ttt_values[row][col])
return -1;
OR if ((b->moves[XS] | b->moves[OS] | ttt_values[row][col]) == (b->moves[XS] | b->moves[OS]))
return -1;
OR if ((b->moves[XS] + b->moves[OS]) & ttt_values[row][col])
return -1;
OR if ((b->moves[p] ^ ttt_values[row][col]) < b->moves[p])
return -1;
etc.
QUESTION 1B (3 points). Complete the following function. You may use the following helper function:
int popcount(unsigned n)
Return the number of 1 bits in n
. (Stands for “population count”; is
implemented on recent x86 processors by a single instruction, popcnt
.)
For full credit, your code should consist of a single “return
”
statement with a simple expression, but for substantial partial credit
write any correct solution.
// Return the number of moves that have happened so far.
int tictactoe_nmoves(const tictactoe* b) {
3 points. You lose at most 1 point for complex expressions in B and F combined.
return popcount(b->moves[XS] | b->moves[OS]);
}
QUESTION 1C (2 points). Write a simple expression that, if nonzero,
indicates that player XS
has a win on board b
across the main
diagonal (has marks in positions 0,0
, 1,1
, and 2,2
).
2 points
(b->moves[XS] & 0x421) == 0x421
Lydia Davis notices Brenda’s code and has a brainstorm. “If you use different values,” she suggests, “it becomes easy to detect any win.” She suggests:
static const unsigned ttt_values[3][3] = {
{ 0x01001001, 0x00010002, 0x10100004 },
{ 0x00002010, 0x22020020, 0x00200040 },
{ 0x40004100, 0x00040200, 0x04400400 }
};
QUESTION 1D (2 points). Repeat Question 1A for Lydia’s values: Write a snippet of C code that returns –1 if an attempted move is reusing a position. This snippet will replace line 3 in Brenda’s code.
2 points. The same code works.
if ((b->moves[XS] | b->moves[OS]) & ttt_values[row][col])
return -1;
QUESTION 1E (2 points). Repeat Question 1B for Lydia’s values: Use
popcount
to complete tictactoe_nmoves
.
int tictactoe_nmoves(const tictactoe* b) {
2 points
return popcount((b->moves[0] | b->moves[1]) & 0x777);
`**`OR`**` return popcount((b->moves[0] | b->moves[1]) & 0x777000);
}
QUESTION 1F (3 points). Complete the following function for Lydia’s
values. For full credit, your code should consist of a single “return
”
statement containing exactly two constants, but for substantial partial
credit write any correct solution.
` // Return nonzero if player `p` has won, 0 if `p` has not won. `
int tictactoe_check_win(const tictactoe* b, int p) {
assert(p == XS || p == OS);
3 points
return (b->moves[p] + 0x11111111) & 0x88888888;
Here’s another amazing possibility (Allen Chen and others):
return b->moves[p] & (b->moves[p] << 1) & (b->moves[p] << 2);
}
2. Where’s Waldo? (15 points)
In the following questions, we give you C code and a portion of the
assembly generated by some compiler for that code. (Sometimes we blank
out a part of the assembly.) The C code contains a variable, constant,
or function called waldo
, and a point in the assembly is marked with
asterisks ***
. Your job is to find Waldo: write an assembly
expression or constant that holds the value of waldo
at the marked
point. We’ve done the first one for you.
–1 point each for first 2 mistakes, –2 points each for remaining mistakes
NON-QUESTION: Where’s Waldo?
int identity(int waldo) {
return waldo;
}
804841d `<identity>`:
804841d: 8b 44 24 04 mov 0x4(%esp),%eax
***
8048421: c3 ret
ANSWER: 4(%esp)
and %eax
both hold the value of waldo
at the
marked point, so either value is a valid answer. If the asterisks came
before the first instruction, only 4(%esp)
would work.
QUESTION 2A: Where’s Waldo?
int f1(int a, int b, int waldo, int d) {
if (a > b)
return waldo;
else
return d;
}
8048422 `<f1>`:
***
8048422: 8b 44 24 08 mov 0x8(%esp),%eax
8048426: 39 44 24 04 cmp %eax,0x4(%esp)
804842a: 7e 05 jle 8048431 <f1+0xf>
804842c: 8b 44 24 0c mov 0xc(%esp),%eax
8048430: c3 ret
8048431: 8b 44 24 10 mov 0x10(%esp),%eax
8048435: c3 ret
0xc(%esp)
QUESTION 2B: Where’s Waldo?
int int_array_get(int* a, int waldo) {
int x = a[waldo];
return x;
}
8048436 `<int_array_get>`:
INSTRUCTIONS OMITTED
***
804843e: 0f be 04 02 mov (%edx,%eax,4),%eax
8048442: c3 ret
%eax
QUESTION 2C: Where’s Waldo?
int matrix_get(int** matrix, int row, int col) {
int* waldo = matrix[row];
return waldo[col];
}
8048443 `<matrix_get>`:
8048443: 8b 54 24 08 mov 0x8(%esp),%edx
8048447: 8b 44 24 04 mov 0x4(%esp),%eax
***
804844b: ?? ?? ?? mov ??,%eax
804844e: 8b 54 24 0c mov 0xc(%esp),%edx
8048452: 8b 04 90 mov (%eax,%edx,4),%eax
8048455: c3 ret
(%eax,%edx,4)
QUESTION 2D: Where’s Waldo?
int f5(int x) {
extern int waldo(int);
return waldo(x * 45);
}
8048534 `<f5>`:
***
8048534: 8b 44 24 04 mov 0x4(%esp),%eax
8048538: b9 2d 00 00 00 mov $0x2d,%ecx
804853d: f7 e1 mul %ecx
804853f: 89 44 24 04 mov %eax,0x4(%esp)
8048543: e9 c8 ff ff ff jmp 0x8048510
0x8048510
QUESTION 2E: Where’s Waldo?
int factorial(int waldo) {
if (waldo < 2)
return 1;
else
return waldo * factorial(waldo - 1);
}
8048494 `<factorial>`:
8048494: 8b 54 24 04 mov 0x4(%esp),%edx
8048498: b8 01 00 00 00 mov $0x1,%eax
804849d: 83 fa 01 cmp $0x1,%edx
80484a0: 7f 04 jg .L2 <factorial+0x12>
80484a2: eb 0d jmp .L3 <factorial+0x1d>
.L1:
***
80484a4: 89 ca mov %ecx,%edx
.L2: 80484a6: 8d 4a ff lea -0x1(%edx),%ecx
80484a9: 0f af c2 imul %edx,%eax
80484ac: 83 f9 01 cmp $0x1,%ecx
80484af: 75 f3 jne .L1 <factorial+0x10>
.L3: 80484b1: c3 ret
%ecx
QUESTION 2F: Where’s Waldo?
int binary_search(const char* needle, const char** haystack, unsigned sz) {
unsigned waldo = 0, r = sz;
while (waldo < r) {
unsigned m = waldo + ((r - waldo) >> 1);
if (strcmp(needle, haystack[m]) < 0)
r = m;
else if (strcmp(needle, haystack[m]) == 0)
waldo = r = m;
else
waldo = m + 1;
}
return waldo;
}
80484ab `<binary_search>`:
INSTRUCTIONS OMITTED
.L1: 80484c3: 89 fe mov %edi,%esi
80484c5: 29 de sub %ebx,%esi
80484c7: d1 ee shr %esi
80484c9: 01 de add %ebx,%esi
80484cb: 8b 44 b5 00 mov 0x0(%ebp,%esi,4),%eax
80484cf: 89 44 24 04 mov %eax,0x4(%esp)
80484d3: 8b 44 24 30 mov 0x30(%esp),%eax
80484d7: 89 04 24 mov %eax,(%esp)
80484da: e8 11 fe ff ff call 80482f0 <strcmp@plt>
80484df: 85 c0 test %eax,%eax
80484e1: 78 09 js .L2 <binary_search+0x41>
80484e3: 85 c0 test %eax,%eax
80484e5: 74 13 je 80484fa <binary_search+0x4f>
***
80484e7: 8d 5e 01 lea 0x1(%esi),%ebx
80484ea: eb 02 jmp .L3 <binary_search+0x43>
.L2: 80484ec: 89 f7 mov %esi,%edi
.L3: 80484ee: 39 df cmp %ebx,%edi
80484f0: 77 d1 ja .L1 <binary_search+0x18>
INSTRUCTIONS OMITTED
%ebx
In the remaining questions, you are given assembly compiled from one of the above functions by a different compiler, or at a different optimization level. Your goal is to figure out what C code corresponds to the given assembly.
QUESTION 2G:
804851d `<waldo>`:
804851d: 55 push %ebp
804851e: 89 e5 mov %esp,%ebp
8048520: 83 ec 18 sub $0x18,%esp
8048523: 83 7d 08 01 cmpl $0x1,0x8(%ebp)
8048527: 7f 07 jg 8048530
8048529: b8 01 00 00 00 mov $0x1,%eax
804852e: eb 10 jmp 8048540
8048530: 8b 45 08 mov 0x8(%ebp),%eax
8048533: 48 dec %eax
8048534: 89 04 24 mov %eax,(%esp)
8048537: e8 e1 ff ff ff call 804851d
804853c: 0f af 45 08 imul 0x8(%ebp),%eax
8048540: c9 leave
8048541: c3 ret
What’s Waldo? Circle one.
|
|
|
5. factorial
QUESTION 2H:
8048425 `<waldo>`:
8048425: 55 push %ebp
8048426: 89 e5 mov %esp,%ebp
8048428: 8b 45 08 mov 0x8(%ebp),%eax
804842b: 3b 45 0c cmp 0xc(%ebp),%eax
804842e: 7e 05 jle 8048435 <waldo+0x10>
8048430: 8b 45 10 mov 0x10(%ebp),%eax
8048433: eb 03 jmp 8048438 <waldo+0x13>
8048435: 8b 45 14 mov 0x14(%ebp),%eax
8048438: 5d pop %ebp
8048439: c3 ret
What’s Waldo? Circle one.
|
|
|
1. f1
QUESTION 2I:
80484a1 `<waldo>`:
80484a1: 55 push %ebp
80484a2: 89 e5 mov %esp,%ebp
80484a4: 83 ec 18 sub $0x18,%esp
80484a7: 8b 55 08 mov 0x8(%ebp),%edx
80484aa: 89 d0 mov %edx,%eax
80484ac: c1 e0 02 shl $0x2,%eax
80484af: 01 d0 add %edx,%eax
80484b1: 01 c0 add %eax,%eax
80484b3: 01 d0 add %edx,%eax
80484b5: c1 e0 02 shl $0x2,%eax
80484b8: 01 d0 add %edx,%eax
80484ba: 89 04 24 mov %eax,(%esp)
80484bd: e8 2b 01 00 00 call 80485ed
80484c2: c9 leave
80484c3: c3 ret
What’s Waldo? Circle one.
|
|
|
2. f5
3. Kernel programming (15 points)
WeensyOS processes are quite isolated: the only way they can communicate is by using the console. Let’s design some system calls that will allow processes to explicitly share pages of memory. Then the processes can communicate by writing and reading the shared memory region. Here are two new WeensyOS system calls that allow minimal page sharing; they return 0 on success and –1 on error.
int share(pid_t p, void* addr)
Allow process p
to access the page at address addr
.
int attach(pid_t p, void* remote_addr, void* local_addr)
Access the page in process p
’s address space at address remote_addr
.
That physical page is added to the calling process’s address space at
address local_addr
, replacing any page that was previously mapped
there. It is an error if p
has not shared the page at remote_addr
with the calling process.
Here’s an initial implementation of these system calls, written as
clauses in the WeensyOS kernel’s exception
function. The appendix has
a copy of this code, as well as some WeensyOS documentation and constant
definitions.
case INT_SYS_SHARE: {
pid_t p = current->p_registers.reg_eax;
uintptr_t addr = current->p_registers.reg_ecx;
//
[A]
int shindex = current->p_nshared;
if (shindex >= MAX_NSHARED)
goto return_error;
//
[B]
++current->p_nshared;
current->p_shared[shindex].sh_addr = addr;
current->p_shared[shindex].sh_partner = p;
current->p_registers.reg_eax = 0;
break;
}
case INT_SYS_ATTACH: {
pid_t p = current->p_registers.reg_eax;
uintptr_t remote_addr = current->p_registers.reg_ecx;
uintptr_t local_addr = current->p_registers.reg_edx;
//
[C]
int shindex = -1;
for (int i = 0; i < processes[p].p_nshared; ++i)
if (processes[p].p_shared[i].sh_addr == remote_addr
&& processes[p].p_shared[i].sh_partner == current->p_pid)
shindex = i;
if (shindex == -1)
goto return_error;
//
[D]
vamapping vam = virtual_memory_lookup(processes[p].p_pagetable, remote_addr);
//
[E]
virtual_memory_map(current->p_pagetable, local_addr,
vam.pa, PAGESIZE, PTE_P|PTE_W|PTE_U);
//
[F]
current->p_registers.reg_eax = 0;
break;
}
return_error:
current->p_registers.reg_eax = -1;
break;
Some notes:
- The implementation stores sharing records in an array. A process may
call
share
successfully at mostMAX_NSHARED
times. After that, its futureshare
calls will return an error. processes[p].p_nshared
is initialized to 0 for all processes.- Assume that WeensyOS has been implemented as in Problem Set 4 up through step 6 (shared read-only memory).
2 points for each T/F, 5 points for 3F.
QUESTION 3A. True or false: Given this implementation, a single
WeensyOS process can cause the kernel to crash simply by calling share
one or more times (with no process ever calling attach
). If true, give
an example of a call or calls that would likely crash the kernel.
False
QUESTION 3B. True or false: Given this implementation, a single
WeensyOS process can cause the kernel to crash simply by calling
attach
one or more times (with no process ever calling share
). If
true, give an example of a call or calls that would likely crash the
kernel.
True. If the user supplies an out-of-range process ID argument, the
kernel will try to read out of bounds of the processes
array. Example
call: attach(0x1000000, 0, 0)
.
QUESTION 3C. True or false: Given this implementation, WeensyOS
processes 2 and 3 could work together to obtain write access to the
kernel code located at address KERNEL_START_ADDR
. If true, give an
example of calls that would obtain this access.
True, since the attach
and share
code don’t check whether the user
process is allowed to access its memory. An example:
#2: share(3, KERNEL_START_ADDR)
#3: attach(2, KERNEL_START_ADDR, 0x110000)
QUESTION 3D. True or false: Given this implementation, WeensyOS processes 2 and 3 could work together to obtain write access to any memory, without crashing or modifying kernel code or data. If true, give an example of calls that would obtain access to a page mapped at address 0x110000 in process 5.
The best answer here is false. Processes are able to gain access to any
page mapped in one of their page tables. But it’s not clear whether 5’s
0x110000 is mapped in either of the current process’s page tables. Now,
2 and 3 could first read the processes
array (via share/attach) to
find the physical address of 5’s page table; then, if 2 and 3 are in
luck and the page table itself is mapped in their page table, they could
read that page table to find the physical address of 0x110000; and then,
if 2 and 3 are in luck again, map that page using the VA accessible in
one of their page tables (which would differ from 0x110000). But that
might not work.
QUESTION 3E. True or false: Given this implementation, WeensyOS
child processes 2 and 3 could work together to modify the code run by a
their shared parent, process 1, without crashing or modifying kernel
code or data. If true, give an example of calls that would obtain write
access to process 1’s code, which is mapped at address
PROC_START_ADDR
.
True; since process code is shared after step 6, the children can map their own code read/write, and this is the same code as the parent’s.
#2: share(3, PROC_START_ADDR)
#3: attach(2, PROC_START_ADDR, PROC_START_ADDR)
QUESTION 3F. Every “true” answer to the preceding questions is a bug in WeensyOS’s process isolation. Fix these bugs. Write code snippets that address these problems, and say where they go in the WeensyOS code (for instance, you could refer to bracketed letters to place your snippets); or for partial credit describe what your code should do.
5 points. Here’s one possibility.
Prevent share
from sharing an invalid address:
[A] if ((addr & 0xFFF) || addr < PROC_START_ADDR)
return -1;
NB don’t need to check addr < MEMSIZE_VIRTUAL
as long as we check the
return value from virtual_memory_lookup
below (but that doesn’t hurt).
Prevent attach
from accessing an invalid process or mapping at an
invalid address:
[C] if (p >= NPROC || (local_addr & 0xFFF) || local_addr < PROC_START_ADDR || local_addr >= MEMSIZE_VIRTUAL)
return -1;
We do need to check MEMSIZE_VIRTUAL
here.
Check the mapping at remote_addr
before installing it:
[E] if (!(vam.perm & PTE_U)
return -1;
In virtual_memory_map: Use vam.perm instead of PTE_U|PTE_P|PTE_W
For greatest justice we would also fix a potential memory leak caused by
attach
ing over an address that already had a page, but this isn’t
necessary.
4. Pipes and synchronization (20 points)
In the following questions, you will implement a mutex using a pipe, and a limited type of pipe using a mutex.
The definitions of the pthread mutex and condition variable operations are as follows.
int pthread_mutex_init(pthread_mutex_t* m, const pthread_mutexattr_t* attr)
Create a new mutex with attributes defined by attr
. (For this
question, attr
is ignored.)
int pthread_mutex_lock(pthread_mutex_t* m)
Locks m
. If the mutex is already locked, the calling thread will block
until the mutex becomes available.
int pthread_mutex_unlock(pthread_mutex_t* m)
Unlocks m
. Calling pthread_mutex_unlock
with a mutex that the
calling thread does not hold will result in undefined behavior.
int pthread_cond_init(pthread_cond_t* c, const pthread_condattr_t* attr)
Create a new condition variable with attributes defined by attr
. (For
this question, attr
is ignored.)
int pthread_cond_signal(pthread_cond_t* c)
Unblocks one thread waiting for c
.
int pthread_cond_wait(pthread_cond_t* c, pthread_mutex_t* m)
Atomically unlocks m
and blocks the calling thread on the condition
c
. When the condition is signaled, the thread locks m
and returns.
Calling pthread_cond_wait
with an unlocked mutex will result in
undefined behavior.
The operations return 0 on success. Although errors are possible (for
instance, ENOMEM
if there’s not enough memory to allocate a new mutex)
you may assume that they don’t occur.
QUESTION 4A. In this question, you are to implement mutex
functionality using a pipe. Fill in the definitions of
pipe_mutex_init
, pipe_mutex_lock
, and pipe_mutex_unlock
. You
should be able to implement the same functionality as the pthread
versions (assuming no other code accesses the pipe).
4 points
typedef struct pipe_mutex {
int fd[2];
} pipe_mutex;
int pipe_mutex_init(pipe_mutex* m) {
if (pipe(&m->fd) < 0)
return -1;
write(m->fd[1], "X", 1);
return 0;
}
int pipe_mutex_lock(pipe_mutex* m) {
char buf;
read(m->fd[0], &buf, 1);
A while loop would be in some ways even better, but you were allowed to assume no rando error returns.
}
int pipe_mutex_unlock(pipe_mutex* m) {
write(m->fd[1], "X", 1);
}
In the next questions, you will help implement pipe functionality using an in-memory buffer and a mutex. This “mutex pipe” will only work between threads of the same process (in contrast to a regular pipe, which also works between processes). An initial implementation of mutex pipes is as follows; you will note that it contains no mutexes.
typedef struct mutex_pipe {
1.
char buf[BUFSIZ];
2.
size_t head;
3.
size_t sz;
} mutex_pipe;
int mutex_pipe_init(mutex_pipe* p) {
6.
p->head = p->sz = 0;
7.
memset(&p->buf[0], 0, sizeof(p->buf));
8.
return 0;
}
` // Read up to `sz` bytes from the mutex_pipe into `buf` and return the number of bytes `
// read. If no bytes are available, wait until at least one byte can be read.
ssize_t mutex_pipe_read(mutex_pipe* p, char* buf, size_t sz) {
10.
size_t n = 0;
11.
while (n < sz && (p->sz != 0 || n == 0)) {
12.
size_t ncopy = p->sz;
13.
if (ncopy > sizeof(p->buf) - p->head)
14.
ncopy = sizeof(p->buf) - p->head;
15.
if (ncopy > sz - n)
16.
ncopy = sz - n;
17.
memcpy(&buf[n], &p->buf[p->head], ncopy);
18.
n += ncopy;
19.
p->head += ncopy;
20.
p->head = p->head % sizeof(p->buf);
21.
p->sz -= ncopy;
22.
}
23.
return n;
}
` // Write up to `sz` bytes from `buf` into the mutex_pipe and return the number of bytes `
// written. If no space is available, wait until at least one byte can be written.
ssize_t mutex_pipe_write(mutex_pipe* p, const char* buf, size_t sz) {
30.
size_t n = 0;
31.
while (n < sz && (p->sz != sizeof(p->buf) || n == 0)) {
32.
size_t tail = p->head + p->sz;
33.
tail = tail % sizeof(p->buf);
34.
size_t ncopy = sizeof(p->buf) - p->sz;
35.
if (ncopy > sizeof(p->buf) - tail)
36.
ncopy = sizeof(p->buf) - tail;
37.
if (ncopy > sz - n)
38.
ncopy = sz - n;
39.
memcpy(&p->buf[tail], &buf[n], ncopy);
40.
n += ncopy;
41.
p->sz += ncopy;
42.
}
43.
return n;
}
The last page of this exam has a copy of that code that you can remove and keep.
NOT A QUESTION.
It would be wise to work through an example. For example, assume
BUFSIZ == 4
, and figure out how the following calls would behave.
mutex_pipe_write(p, "Hi", 2);
mutex_pipe_read(p, buf, 4);
mutex_pipe_write(p, "Test", 4);
mutex_pipe_read(p, buf, 3);
First let’s reason about this code in the absence of threads.
QUESTION 4B. Which of the following changes could, if made in isolation, result in undefined behavior when a mutex pipe was used? Circle all that apply.
- Eliminating line 6
- Eliminating line 7
- Eliminating lines 13–14
- Eliminating lines 15–16
- Eliminating line 18
- Eliminating line 19
6 points for all of 4B–4D. 0–2 mistakes full credit; –1 point for every 2 additional mistakes.
6, 13–14, and 15–16. Grading Notes
All three sections are graded together. No single section should cause you to lose more than 2; the first two wrong don’t count.
6: Accesses to uninitialized variables cause undefined behavior.
13–14: Could cause accesses off the end of p->buf
.
15–16: Could cause accesses off the end of buf
.
7: If this is the only change, no problem; the existing code never
accesses bytes that were not written by mutex_pipe_write
.
18: This causes mutex_pipe_read
to spin forever (since n
is not
increased), but that’s not undefined.
19: This causes mutex_pipe_read
to read the same data over and over
again (since p->head
never advances), but that’s not undefined.
QUESTION 4C. Which of the following changes could, if made in
isolation, cause a mutex_pipe_read
to return incorrect data (that is,
the byte sequence produced by read
will not equal the byte sequence
passed to write
)? Circle all that apply.
- Eliminating line 33
- Eliminating lines 35–36
- Eliminating lines 37–38
- Eliminating line 39
- Eliminating line 40
- Eliminating line 41
35–36, 37–38, and 39.
35–36: Copies some of the written data past the end of the buffer. Not
only does this cause undefined behavior, the data’s lost to the
reader.
37–38: Copies some unwritten data (data past the end of the write
buffer) into the pipe.
39: Take this away and nothing gets written to the buffer! But the size
still grows so the reader thinks there’s data there.
33: This is a tricky one. Here’s what happens: No mutex_pipe_write
can
write data that “wraps around” the buffer. Assume BUFSIZ == 4
,
p->head == 3
, p->sz == 1
, and mutex_pipe_write(p, "X", 1)
is
called. Basically tail
is set to 4
, and lines 35–36 will set
tail = 0
! So then mutex_pipe_write
will spin forever; but in the
meantime mutex_pipe_read
will not read anything incorrect.
40: n
never advances, so the same portion of the data (the first
portion) is written over and over again into the pipe until it fills up.
This leaves the pipe in a bad state—containing data that was never
written in that order—but then mutex_pipe_write
spins forever, so
the reader can never read it.
41: Doesn’t advance sz
: the buffer always appears empty, so the reader
never observes incorrect data.
It should be considered OK to select #40.
QUESTION 4D. Which of the following changes could, if made in
isolation, cause a call to mutex_pipe_write
to never return (when a
correct implementation would return)? Circle all that apply.
- Eliminating line 33
- Eliminating lines 35–36
- Eliminating lines 37–38
- Eliminating line 39
- Eliminating line 40
- Eliminating line 41
33, 35–36, 37–38, and 40.
33 and 40: covered above. 35–36 and 37–38: undefined behavior can cause anything to happen! Maybe no points off for this, though.
QUESTION 4E. Write an invariant for p->sz
. An invariant is a
statement about the value of p->sz
that is always true. Write your
invariant in the form of an assertion; for full credit give the most
specific true invariant you can. (“p->sz
is an integer” is unspecific,
but true; “p->sz == 4
” is specific, but false.)
2 points.
assert( p->sz >= 0 && p->sz <= BUFSIZ );
But in fact p->sz
is a size_t
, so p->sz >= 0
is a tautology and
assert(p->sz <= BUFSIZ)
works too.
QUESTION 4F. Write an invariant for p->head
. For full credit give
the most specific true invariant you can.
2 points.
assert( p->head >= 0 && p->head < BUFSIZ );
Again, assert(p->head < BUFSIZ)
is equivalent.
In the remaining questions, you will add synchronization objects and operations to make your mutex pipe work in a multithreaded program. Here is your starting point:
typedef struct mutex_pipe {
1.
char buf[BUFSIZ];
2.
size_t head;
3.
size_t sz;
4.
pthread_mutex_t m;
} mutex_pipe;
int mutex_pipe_init(mutex_pipe* p) {
5.
pthread_mutex_init(&p->m, NULL);
6.
p->head = p->sz = 0;
7.
memset(&p->buf[0], 0, sizeof(p->buf));
8.
return 0;
}
(the rest of the code as in the prior questions)
QUESTION 4G. Add calls to “lock
” (pthread_mutex_lock
) and
“unlock
” (pthread_mutex_unlock
) that protect the mutex pipe from
race condition bugs. Write one or more snippets of C code and give line
numbers after which the snippets should appear. For full credit, your
solution must not deadlock—if one thread is reading from a pipe and
another thread is writing to the pipe, then both threads must eventually
make progress.
- Add
pthread_mutex_lock(&p->m);
after lines: 10, 30 - Add
pthread_mutex_unlock(&p->m);
after lines: 22, 42 - Other changes (if any):
6 points for 4G & 4H together.
After #17 & #39:
if (n == 0) {
pthread_mutex_unlock(&p->m); // or just "unlock"
sched_yield(); // optional
pthread_mutex_lock(&p->m); // or just "lock"
}
Some people might put a sched_yield()
in: nice!
QUESTION 4H. Your solution to the last question has poor
utilization. For instance, a thread that calls mutex_pipe_read
on an
empty mutex pipe will spin forever, rather than block. Introduce one or
more condition variables so that mutex_pipe_read
will block until data
is available. Write one or more snippets of C code and give line numbers
after which the snippets should appear.
- Add to
struct mutex_pipe
:pthread_cond_t c;
- Add to
mutex_pipe_init
after line 7:pthread_cond_init(&c, NULL);
- Other changes:
6 points for 4G & 4H together.
After #17, instead of the code above:
if (n == 0)
pthread_cond_wait(&p->c, &p->m);
After #39:
if (n != 0)
pthread_cond_signal(&p->c);
(This can go anywhere after n
is calculated.)
5. Race conditions (15 points)
Most operating systems support process priority levels, where the kernel runs higher-priority processes more frequently than lower-priority processes. A hypothetical Unix-like operating system called “Boonix” has two priority levels, normal and batch. A Boonix parent process changes the priority level of one of its children with this system call:
int setbatch(pid_t p)
Sets process p
to have batch priority. All future children of p
will
also have batch priority. Returns 0 on success, –1 on error. Errors
include ESRCH
, if p
is not a child of the calling process.
Note that a process cannot change its own batch status.
You’re writing a Boonix shell that can run commands with batch priority.
If c->isbatch
is nonzero, then c
should run with batch priority, as
should its children. Your start_command
function looks like this:
pid_t start_command(command* c) {
1.
c->pid = fork();
2.
if (c->pid == 0) {
3.
handle_pipes(c);
4.
handle_redirections(c);
5.
(void) execvp(c->argv[0], c->argv);
6.
// if we get here, execvp failed
7.
perror("execvp");
8.
exit(1);
9.
}
10.
assert(c->pid > 0);
11.
if (c->isbatch)
12.
setbatch(c->pid);
13.
return c->pid;
}
This shell has two race conditions, one more serious.
QUESTION 5A. In some cases, c
will change to batch priority after
it starts running. Draw a dependency diagram demonstrating this race
condition, or briefly describe it.
2 points. This happens if the child manages to execvp
before the
parent calls setbatch
.
QUESTION 5B. In some cases, c
or one of its children could run
forever with normal priority. Draw a dependency diagram demonstrating
this race condition, or briefly describe it.
2 points. This happens if the child execvp
s, and then fork
s another
child, before the parent calls setbatch
. The grandchild will stick at
normal priority.
In the remaining questions, you will fix these race conditions in three different ways. The first uses a new system call:
int isbatch()
Returns 1 if the calling process has batch priority, 0 if it has normal
priority.
QUESTION 5C. Use isbatch
to prevent both race conditions. Write a
snippet of C code and give the line number after which it should appear.
You should need one code snippet.
3 points. After #2:
while (c->isbatch && !isbatch())
/* spin */;
QUESTION 5D. Use the pipe
system call and friends to prevent both
race conditions. Write snippets of C code and give the line numbers
after which they should appear. You should need several snippets. Make
sure you clean up any extraneous file descriptors before running the
command or returning from start_command
.
2 points. A lot of different ways to do this. Here we create the pipe
always but use it only if c->isbatch
.
After #1:
int pipefd[2];
pipe(pipefd);
After #3:
if (c->isbatch) {
char buf;
read(pipefd[0], &buf, 1);
}
close(pipefd[0]);
close(pipefd[1]);
After #12:
write(pipefd[1], "X", 1);
close(pipefd[0]);
close(pipefd[1]);
This alternate solution relies on end-of-file.
After #1:
int pipefd[2];
pipe(pipefd);
After #3:
close(pipefd[1]);
if (c->isbatch)
read(pipefd[0], &pipefd, 1); // won’t ever read any chars, so this is safe
close(pipefd[0]);
After #12:
close(pipefd[0]);
close(pipefd[1]);
QUESTION 5E. Why should the pipe
solution be preferred to the
isbatch
solution? A sentence, or the right single word, will suffice.
3 points. Utilization. The pipe
will block; the setbatch
polls.
QUESTION 5F. Suggest a change to the setbatch
system call’s
behavior that could fix both race conditions, and say how to use this
new setbatch
in start_command
. Write one or more snippets of C code
and give the line numbers after which they should appear.
3 points. Simple: Allow a process to set its own batchness. Then get rid of the call in the parent. In the child, after #2:
if (c->isbatch)
setbatch(getpid());
6. Debugging (10 points)
In the following short-answer questions, you have access to four
debugging tools: top
, strace
, gdb
, and valgrind
. You can’t
change program source code or use other tools. Answer the questions
briefly (a couple sentences at most).
2 points each
QUESTION 6A. You are given a program that appears to “get stuck” when run. How would you distinguish whether the program blocked forever (e.g., made a system call that never returned) or entered an infinite loop?
You can use top
: does it report the process is using 100% of the CPU?
You can use strace
: is the last thing in the strace an incomplete
system call?
QUESTION 6B. You are given a program that uses a lot of memory. How would you tell whether the program leaks memory?
Use valgrind
and check if it reports any memory leaks.
QUESTION 6C. You are given a program that produces weird answers. How would you check if it invoked undefined behavior?
Use valgrind
and check if it reports undefined behavior. GDB is also
acceptable here.
QUESTION 6D. You are given a program that blocks forever. How would you tell where the program blocked (which function called the blocking system call)?
Run it under gdb
. When it blocks, hit Ctrl-C and then enter
backtrace
/bt
to get a backtrace.
QUESTION 6E. You are given a program that takes a long time to produce a result. How would you tell whether the program was using system calls unintelligently?
Run it under strace
and look for stupidity, such as many system calls
that report errors, many system calls that are redundant, lots of
read
s that return short counts, etc.
7. Miscellany (10 points)
QUESTION 7A. True or false in conventional Unix systems?
3 points. 1 point off for every 2 mistakes
- File descriptors are often used to communicate among processes on the same machine. True
- File descriptors are often used to communicate among processes on different machines. True
- File descriptors are often used to communicate with persistent storage. True
- File descriptors are often used to access primary memory. False
- File descriptors are often used to create child processes. False
QUESTION 7B. Match the process isolation feature on the left with the hardware feature that helps enforce it on the right. Use each hardware feature once (make the best match you can).
3 points
|
|
1—a, 2—d, 3—b, 4—c
The remaining questions refer to the following lines of code.
1.
close(fd);
2.
connect(fd, sockaddr, socklen);
3.
listen(fd);
4.
mmap(NULL, 4096, PROT_READ, MAP_SHARED, fd, 0);
5.
read(fd, buf, 4096);
6.
write(fd, buf, 4096);
4 points for all 3 together. –1 for first mistake.
QUESTION 7C. If a program executes the following line without error, which lines could be executed next without error? List all numbers that apply.
fd = open("/home/cs61user/cs61-psets/pset6/pong61.c", O_RDWR);
1, 4, 5, 6
QUESTION 7D. If a program executes the following line without error, which lines could be executed next without error? List all numbers that apply.
fd = socket(AF_INET, SOCK_STREAM, 0);
1, 2, 3
QUESTION 7E. If a program executes the following lines without error, which lines could be executed next without error? List all numbers that apply.
pipe(pipefd); fd = pipefd[0];
1, 5
Thanks for taking the course!
NOTOC