Sample midterm solutions

First try to answer the questions yourself!

1. Sizes and alignments

QUESTION 1A. True or false: For any type X, the size of X (sizeof(X)) is greater than or equal to the alignment of type X.

QUESTION 1B. True or false: For any type X, the size of struct Y { X a; char newc; } is greater than the size of X.

QUESTION 1C. True or false: For any types A1...An (with n ≥ 1), the size of struct Y is greater than the size of struct X, given:

  struct X {     struct Y {
     A1 a1;         A1 a1;
     ...            ...
     An an;         An an;
  };                char newc;
                 };

QUESTION 1D. True or false: For any types A1...An (with n ≥ 1), the size of struct Y is greater than the size of union X, given:

  union X {      struct Y {
     A1 a1;         A1 a1;
     ...            ...
     An an;         An an;
  };             };

2. Expressions

Solutions here

3. Hello binary

This problem locates 8-bit numbers horizontally and vertically in the following 16x16 image. Black pixels represent 1 bits and white pixels represent 0 bits. For horizontal arrangements, the most significant bit is on the left as usual. For vertical arrangements, the most significant bit is on top.

Examples: The 8-bit number 15 (hexadecimal 0x0F, binary 0b00001111) is located horizontally at 3,4, which means X=3, Y=4.

• The pixel at 3,4 is white, which has bit value 0.
• 4,4 is white, also 0.
• 5,4 is white, also 0.
• 6,4 is white, also 0.
• 7,4 is black, which has bit value 1.
• 8,4, 9,4, and 10,4 are black, giving three more 1s.
• Reading them all off, this is 0b00001111, or 15.

15 is also located horizontally at 7,6.

The 8-bit number 0 is located vertically at 0,0. It is also located horizontally at 0,0 and 1,0.

The 8-bit number 134 (hexadecimal 0x86, binary 0b10000110) is located vertically at 8,4.

QUESTION 3A. Where is 3 located vertically? (All questions refer to 8-bit numbers.)

QUESTION 3B. Where is 12 located horizontally?

QUESTION 3C. Where is 255 located vertically?

4. Hello memory

Shintaro Tsuji wants to represent this image in computer memory. He stores it in an array of 16-bit unsigned integers:

uint16_t cute[16];

Row Y of the image is stored in integer cute[Y].

QUESTION 4A. What is sizeof(cute), 2, 16, 32, or 64?

QUESTION 4B. printf("%d\n", cute[0]); prints 16384. Is Shintaro’s machine big-endian or little-endian?

5. Hello program

Solutions here

6. Memory regions

Consider the following program:

struct ptrs {
    int **x;
    int *y;
};

struct ptrs global;

void setup(struct ptrs *p) {
    int *a = malloc(sizeof(int));
    int *b = malloc(sizeof(int));
    int *c = malloc(sizeof(int));
    int *d = malloc(sizeof(int));
    int *e = malloc(sizeof(int) * 2);
    int **f = malloc(4 * sizeof(int *));
    int **g = malloc(sizeof(int *));

    *a = 0;
    *b = 0;
    *c = (int) a;
    *d = *b;
    e[0] = 29;
    e[1] = (int) &d[100000];

    f[0] = b;
    f[1] = c;
    f[2] = 0;
    f[3] = 0;

    *g = c;

    global.x = f;
    global.y = e;

    p->x = g;
    p->y = &e[1];
}

int main(int argc, char **argv) {
    stack_bottom = (char *) &argc;
    struct ptrs p;
    setup(&p);
    m61_collect();
    do_stuff(&p);
}

This program allocates objects a through g on the heap and then stores those pointers in some stack and global variables. (It then calls our conservative garbage collector from class, but that won’t matter until the next problem.) We recommend you draw a picture of the state setup creates.

QUESTION 6A. Assume that (uintptr_t) a == 0x8300000, and that malloc returns increasing addresses. Match each address to the most likely expression with that address value. The expressions are evaluated within the context of main. You will not reuse an expression.

7. Garbage collection

Here is the top-level function for the conservative garbage collector we wrote in class (cs61-lectures/l07/m61-13.c).

void m61_collect(void) {
    char *stack_top = (char *) &stack_top;

    // The entire contents of the heap start out unmarked
    for (size_t i = 0; i != nmr; ++i)
    mr[i].marked = 0;

    // Mark all reachable objects, starting with the roots (the stack)
    m61_markaccessible(stack_top, stack_bottom - stack_top);

    // Free everything that wasn't marked
    for (size_t i = 0; i != nmr; ++i)
    if (mr[i].marked == 0) {
        m61_free(mr[i].ptr);
        --i;        // m61_free moved different data into this
                // slot, so we must recheck the slot
    }
}

This garbage collector is not correct because it doesn’t capture all memory roots.

Consider the program from the previous section, and assume that an object is reachable if do_stuff can access an address within the object via variable references and memory dereferences without casts or pointer arithmetic. Then:

QUESTION 7A. Which reachable objects will m61_collect() free? Circle all that apply.

QUESTION 7B. Which unreachable objects will m61_collect() not free? Circle all that apply.

a

QUESTION 7C. Conservative garbage collection in C is often slower than precise garbage collection in languages such as Java. Why? Circle all that apply.

1. C is generally slower than other languages.
2. Conservative garbage collectors must search all reachable memory for pointers. Precise garbage collectors can ignore values that do not contain pointers, such as large character buffers.
3. C programs generally use the heap more than programs in other languages.
4. None of the above.

8. Data structures

Solutions

9. Attack

QUESTION 9A. True or false: A successful stack smashing attack against a process can cause that process to execute a cli instruction.

QUESTION 9B. True or false: Buffer overflow attacks would be neutralized if the processor protected stack return addresses so that they couldn’t be overwritten.

QUESTION 9C. “Canary” values can help detect stack smashing attacks before the attacker’s code gains control. Before returning, a function compares one copy of the canary with a reserved copy; if they differ, the stack was smashed. Which properties are valuable in canary values? Circle all that apply.

1. Value predictable in advance
2. One copy located close to the return address on the stack
3. Both copies located close to the return address on the stack
4. Inexpensive to compare
5. None of the above

10. Memory errors

The following function constructs and returns a lower-triangular matrix of size N. The elements are random 2-dimensional points in the unit square. The matrix is represented as an array of pointers to arrays.

 typedef struct point2 {
     double d[2];
 } point2;
 typedef point2 *point2_vector;
 
 point2_vector *make_random_lt_matrix(size_t N) {
     point2_vector *m = (point2_vector *) malloc(sizeof(point2_vector) * N);
     for (size_t i = 0; i < N; ++i) {
         m[i] = (point2 *) malloc(sizeof(point2) * (i + 1));        /* LINE A */
         for (size_t j = 0; j <= i; ++j)
             for (int d = 0; d < 2; ++d)
                 m[i][j].d[d] = drand48();                          /* LINE B */
     }
     return m;
 }

This code is running on an x86 machine (size_t is 32 bits). You may assume that the machine has enough free physical memory and the process has enough available virtual address space to satisfy any malloc() call.

QUESTION 10A. Give a value of N so that, while make_random_lt_matrix(N) is running, no malloc() returns NULL, but a memory error (such as a null pointer dereference or an out-of-bounds dereference) happens on Line A. The memory error should happen specifically when i == 1.

(This problem is probably easier when you write your answer in hexadecimal.)

QUESTION 10B. Give a value of N so that no malloc() returns NULL, and no memory error happens on Line A, but a memory error does happen on Line B.

11. Caches and reference strings

QUESTION 11A. True or false: A direct-mapped cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

QUESTION 11B. True or false: A fully-associative cache with N or more slots can handle any reference string containing ≤N distinct addresses with no misses except for cold misses.

Consider the following 5 reference strings.

QUESTION 11C. Which of the strings might indicate a sequential access pattern? Circle all that apply.

QUESTION 11D. Which of the strings might indicate a strided access pattern with stride >1? Circle all that apply.

The remaining questions concern concatenated permutations of these five strings. For example, the permutation αβγδε refers to this reference string:

We pass such permutations through an initially-empty, fully-associative cache with 3 slots, and observe the numbers of hits.

QUESTION 11E. How many cold misses might a permutation observe? Circle all that apply.

Under LRU eviction, the permutation αβεγδ observes 5 hits as follows. (We annotate each access with “h” for hit or “m” for miss.)

QUESTION 11F. How many hits does this permutation observe under FIFO eviction?

QUESTION 11G. Give a permutation that will observe 8 hits under LRU eviction, which is the maximum for any permutation. There are several possible answers. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 7 hits, etc.)

QUESTION 11H. Give a permutation that will observe 2 hits under LRU eviction, which is the minimum for any permutation. There is one unique answer. (Write your answer as a permutation of αβγδε. For partial credit, find a permutation that has 3 hits, etc.)

12. Cache coherence

QUESTION 12A. True or false: The buffer cache is coherent with respect to disk data.

QUESTION 12B. True or false: An x86 processor cache is coherent with respect to primary memory.

QUESTION 12C. True or false: The standard I/O package’s data cache is coherent with respect to file data.