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 (HUID/DCE 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


_________________________________________________________________	__________________________
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.

f1
f5

matrix_get
permutation_compare

factorial
binary_search

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.

f1
f5

matrix_get
permutation_compare

factorial
binary_search

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.

f1
f5

matrix_get
permutation_compare

factorial
binary_search

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 most MAX_NSHARED times. After that, its future share 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 attaching 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 execvps, and then forks 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 reads 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

Protected control transfer (processes can transfer control to the kernel only at defined entry points)
Memory protection (one process cannot modify another process’s memory)
Interrupt protection (only the kernel can disable interrupts)
CPU protection (the kernel always regains control of the CPU eventually)

Traps
Privileged mode (dangerous instructions fault unless the CPU is in privileged mode)
Timer interrupts
Page tables

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