NOTOC

2016 Midterm Solutions

General overview

Assume a CS61 Appliance running on the x86-64 architecture unless otherwise stated. The points allocated to each problem correspond roughly to how much time we think the problem should take. If you get stuck, move on to the next question. If you’re confused, explain your thinking briefly for potential partial credit.

1. Data representation: Allocation sizes (5 points)

typedef union {
    int f1[4];
    long f2[2];
} my_union;

int main() {
    char* p = malloc(sizeof(char*));
    my_union u;
    my_union* up = &u;
    ....
}

How much user-accessible space is allocated on the stack and/or the heap by each of the following statements? Assume x86-64.

QUESTION 1A. typedef union ... my_union;

QUESTION 1B. char* p = malloc(sizeof(char*));

QUESTION 1C. my_union u;

QUESTION 1D. my_union* up = &u;

2. Data representation: ENIAC (10 points)

Professor Kohler has been busy! He'd developed Eddie's NIfty Awesome Computer (ENIAC). When he built the C compiler for ENIAC, he assigned the following sizes and alignments to C’s fundamental data types. (Assume that every other fundamental type has the same size and alignment as one of these.)

QUESTION 2A. This set of sizes is valid: it obeys all the requirements set by C's abstract machine. Give one different size assignment that would make the set as a whole invalid.

QUESTION 2B. What alignment must the ENIAC malloc guarantee?

For the following two questions, assume the following struct on the ENIAC:

struct s {
    char f1[7];
    char *f2;
    short f3;
    int f4;
};

QUESTION 2C. What is sizeof(struct s)?

QUESTION 2D. What is alignof(struct s)?

The remaining questions refer to this structure definition:

// This include file defines a struct inner, but you do not know anything
// about that structure, just that it exists.
#include "inner.h"

struct outer {
    char f1[3];
    struct inner f2;
    short f3;
    int f4;
};

Indicate for each statement whether the statement is always true, possibly true, or never true on the ENIAC.

QUESTION 2E: sizeof(struct outer) > sizeof(struct inner) (Always / Possibly / Never)

QUESTION 2F: sizeof(struct outer) is a multiple of sizeof(struct inner) (Always / Possibly / Never)

QUESTION 2G: alignof(struct outer) > alignof(struct inner) (Always / Possibly / Never)

QUESTION 2H: sizeof(struct outer) - sizeof(struct inner) < 4 (Always / Possibly / Never)

QUESTION 2I: sizeof(struct outer) - sizeof(struct inner) > 32 (Always / Possibly / Never)

QUESTION 2J: alignof(struct inner) == 2 (Always / Possibly / Never)

3. Undefined behavior (8 points)

Which of the following expressions, instruction sequences, and code behaviors cause undefined behavior? For each question, write Defined or Undefined. (Note that the INT_MAX and UINT_MAX constants have types int and unsigned, respectively.)

QUESTION 3A. INT_MAX + 1 (Defined / Undefined)

QUESTION 3B. UINT_MAX + 1 (Defined / Undefined)

QUESTION 3C.

movq $0x7FFFFFFFFFFFFFFF, %rax
addl $1, %rax

(Defined / Undefined)

QUESTION 3D. Failed memory allocation, i.e., malloc returns NULL (Defined / Undefined)

QUESTION 3E. Use-after-free (Defined / Undefined)

QUESTION 3F. Here are two functions and a global variable:

const char string[128] = ".......";
int read_nth_char(int n) {
    return string[n];
}
int f(int i) {
    if (i & 0x40)
        return read_nth_char(i * 2);
    else
        return i * 2;
}

C’s undefined behavior rules would allow an aggressive optimizing compiler to simplify the code generated for f. Fill in the following function with the simplest C code you can, under the constraint that an aggressive optimizing compiler might generate the same object code for f and f_simplified.

int f_simplified(int i) {

    return i * 2;

4. Bit manipulation (8 points)

It’s common in systems code to need to switch data between big-endian and little-endian representations. This is because networks represent multi-byte integers using big-endian representation, whereas x86-family processors store multi-byte integers using little-endian representation.

QUESTION 4A. Complete this function, which translates an integer from big-endian representation to little-endian representation by swapping bytes. For instance, big_to_little(0x01020304) should return 0x04030201. Your return statement must refer to the u.c array, and must not refer to x.

unsigned big_to_little(unsigned x) {
    union {
        unsigned intval;
        unsigned char c[4];
    } u;
    u.intval = x;

    return (u.c[0] << 24) | (u.c[1] << 16) | (u.c[2] << 8) | u.c[3];

QUESTION 4B. Complete the function again, but this time write a single expression that refers to x (you may refer to x multiple times, of course).

unsigned big_to_little(unsigned x) {

    return ((x & 0xFF) << 24) | ((x & 0xFF00) << 8) | ((x & 0xFF0000) >> 8) | (x >> 24);

QUESTION 4C. Now write the function little_to_big, which will translate a little-endian integer into big-endian representation. You may introduce helper variables or even call big_to_little if that’s helpful.

unsigned little_to_big(unsigned x) { 

    return big_to_little(x);

5. Assembly Language (8 points)

The next four questions pertain to the following four code samples.

f1:
       subq    $8, %rsp
       call    callfunc
       movl    %eax, %edx
       leal    1(%rax,%rax,2), %eax     
       testb   $1, %dl
       jne     .L3
       movl    %edx, %eax
       shrl    $31, %eax
       addl    %edx, %eax
       sarl    %eax
.L3:
       addq    $8, %rsp
       ret

f3:
       subq    $8, %rsp
       call    callfunc
       subl    $97, %eax
       cmpb    $4, %al
       ja      .L2 
       movzbl  %al, %eax
       jmp     *.L4(,%rax,8)
.L4:   
       .quad   .L3     
       .quad   .L9
       .quad   .L6
       .quad   .L7
       .quad   .L8
.L3:   
       movl    $42, %edx
       jmp     .L5
.L6:   
       movl    $4096, %edx
       jmp     .L5
.L7:   
       movl    $52, %edx
       jmp     .L5
.L8:   
       movl    $6440, %edx
       jmp     .L5
.L2:   
       movl    $0, %edx
       jmp     .L5
.L9:
       movl    $61, %edx
.L5:
       movl    $.LC0, %esi
       movl    $1, %edi
       movl    $0, %eax
       call    __printf_chk
       addq    $8, %rsp
       ret
.LC0:
       .string "Sum = %d\n"

f2:
       pushq   %rbx
       xorl    %ebx, %ebx
.L3:
       movl    %ebx, %edi
       addl    $1, %ebx
       call    callfunc
       cmpl    $10, %ebx
       jne     .L3
       popq    %rbx
       ret

f4:
       subq    $40, %rsp
       movl    $1, (%rsp)
       movl    $0, 16(%rsp)
.L2:   
       leaq    16(%rsp), %rsi    
       movq    %rsp, %rdi
       call    callfunc
       movl    16(%rsp), %eax    
       cmpl    %eax, (%rsp)
       jne     .L2
       addq    $40, %rsp
       ret

6. Calling conventions: 6186 (15 points)

University Professor Helen Vendler is designing a poetic new processor, the 6186. Can you reverse-engineer some aspects of the 6186’s calling convention from its assembly?

Here’s a function:

int f(int* a, unsigned b) {
    extern int g(int x);
    int index = g(a[2*b + 1]);
    return a[index + b];
}

And here’s that function compiled into 6186 instructions.

f:
    sub $24, %rsp
    movq %ra, (%rsp)
    mov %rb, %rx
    shl $1, %rx
    add $1, %rx
    movl (%ra, %rx, 4), %ra
    call g
    add %rb, %rr
    movq (%rsp), %ra
    movl (%ra, %rr, 4), %ra
    mov %ra, %rr
    add $24, %rsp
    ret

6186 assembly syntax is based on x86-64 assembly, and like the x86-64, 6186 registers are 64 bits wide. However, the 6186 has a different set of registers. There are just five general-purpose registers, %ra, %rb, %rr, %rx, and %ry. (“[W]hen she tries to be deadly serious she is speaking under…constraint”.) The example also features the stack pointer register, %rsp.

Give brief explanations if unsure.

QUESTION 6A. Which register holds function return values?

%rr

QUESTION 6B. What is sizeof(int) on the 6186?

QUESTION 6C. Which general-purpose register(s) must be callee-saved?

%rb

QUESTION 6D. Which general-purpose register(s) must be caller-saved?

%rr`, `%ra`, `%rx

QUESTION 6E. Which general-purpose register(s) might be callee-saved or caller-saved (you can’t tell which)?

%ry

QUESTION 6F. Assuming the compiler makes function stack frames as small as possible given the calling convention, what is the alignment of stack frames?

QUESTION 6G. Assuming that the 6186 supports the same addressing modes as the x86-64, write a single instruction that has the same effect on %ra as these three instructions:

shl $1, %rx
add $1, %rx
movl (%ra, %rx, 4), %ra

movl 4(%ra, %rx, 8), %ra

7. Caching: Reference strings (10 points)

The following questions concern the FIFO (First In First Out), LRU (Least Recently Used), and LFU (Least Frequently Used) cache eviction policies.

Your answers should refer to seven-item reference strings made up of digits in the range 0–9. An example answer might be “1231231”. In each case, the reference string is processed by a 3-slot cache that’s initially empty.

QUESTION 7A. Give a reference string that has a 1/7 hit rate in all three policies.

QUESTION 7B. Give a reference string that has a 6/7 hit rate in all three policies.

QUESTION 7C. Give a reference string that has different hit rates under LRU and LFU policies, and compute the hit rates.

QUESTION 7D. Give a reference string that has different hit rates under FIFO and LRU policies, and compute the hit rates.

QUESTION 7E. Now let's assume that you know a reference string in advance. Given a 3-slot cache and the following reference string, what caching algorithm discussed in class and/or exercises would produce the best hit rate, and would would that hit rate be?

“12341425321521”

8. Caching: Access times and hit rates (5 points)

Recall that x86-64 instructions can access memory in units of 1, 2, 4, or 8 bytes at a time. Assume we are running on an x86-64-like machine with 1024-byte cache lines. Our machine takes 32ns to access a unit if the cache hits, regardless of unit size. If the cache misses, an additional 8160ns are required to load the cache, for a total of 8192ns.

QUESTION 8A. What is the average access time per access to access all the data in a cache line as an array of 256 integers, starting from an empty cache? (2 points total, 1 point for an attempt that shows some understanding)

QUESTION 8B. What unit size (1, 2, 4, or 8) minimizes the access time to access all data in a cache line, starting from an empty cache? (3 points for 5B and 5C, 1 point for writing anything, 1 point for each correct answer)

QUESTION 8C. What unit size (1, 2, 4, or 8) maximizes the hit rate to access all data in a cache line, starting from an empty cache?

9. Single-slot cache code (14 points)

Donald Duck is working on a single-slot cache for reading. He’s using the pos_tag/end_tag representation, which is:

struct io61_file {
   int fd;
   unsigned char cbuf[BUFSIZ];
   off_t tag;      // file offset of first character in cache (same as before)
`    off_t end_tag;  // file offset one past last valid char in cache; end_tag - tag == old `csz` `
`    off_t pos_tag;  // file offset of next char to read in cache; pos_tag - tag == old `cpos` `
};

Here’s our solution code; in case you want to scribble, the code is copied in the appendix.

 1.  ssize_t io61_read(io61_file* f, char* buf, size_t sz) {
 2.      size_t pos = 0;
 3.      while (pos != sz) {
 4.          if (f->pos_tag < f->end_tag) {
 5.              ssize_t n = sz - pos;
 6.              if (n > f->end_tag - f->pos_tag)
 7.                  n = f->end_tag - f->pos_tag;
 8.              memcpy(&buf[pos], &f->cbuf[f->pos_tag - f->tag], n);
 9.              f->pos_tag += n;
10.              pos += n;
11.          } else {
12.              f->tag = f->end_tag;
13.              ssize_t n = read(f->fd, f->cbuf, BUFSIZ);
14.              if (n > 0)
15.                  f->end_tag += n;
16.              else
17.                  return pos ? pos : n;
18.          }
19.      }
20.      return pos;
21.  }

Donald has ideas for “simplifying” this code. Specifically, he wants to try each of the following independently:

QUESTION 9A. Which simplifications could lead to undefined behavior? List all that apply or say “none.”

QUESTION 9B. Which simplifications could cause io61_read to loop forever without causing undefined behavior? List all that apply or say “none.”

QUESTION 9C. Which simplifications could lead to io61_read returning incorrect data in buf, meaning that the data read by a series of io61_read calls won’t equal the data in the file? List all that apply or say “none.”

QUESTION 9D. Chastened, Donald decides to optimize the code for a specific situation, namely when io61_read is called with a sz that is larger than BUFSIZ. He wants to add code after line 11, like so, so that fewer read system calls will happen for large sz:

11.          } else if (sz - pos > BUFSIZ) {
                 // DONALD’S CODE HERE

11A.         } else {
12.              f->tag = f->end_tag;
                 ....

Finish Donald’s code. Your code should maintain the relevant invariants between tag, pos_tag, end_tag, and the file position, but you need not keep tag aligned.

ssize_t n = read(f->fd, &buf[pos], sz - pos);
if (n > 0) {
    f->tag = f->pos_tag = f->end_tag = f->end_tag + n;
    pos += n;
} else
    return pos ? pos : n;